九大排序算法的手写实现及时空复杂度分析

ゝ一世哀愁。 2022-05-24 23:24 101阅读 0赞

一、冒泡排序  
冒泡排序是一种简单的排序方法，算法如下：  
1. 首先将所有待排序的数字放入工作列表中。  
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。  
3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推…)，直至再也不能交换。  
代码实现如下：

#include <iostream>
    using namespace std;
    /*交换函数，作用是交换数组中的两个元素的位置*/
    void swap(int array[],int i,int j)
    {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /*冒泡排序*/
    void BubbleSort(int array[],int n)
    {
        for(int i=0;i<n-1;i++)
        {
            for(int j=n-1;j>i;j--)
            {
                if(array[j]<array[j-1])
                    swap(array,j,j-1);
            }
        }
    }
    int main()
    {
        int array[5]={
       3,1,2,5,4};
        BubbleSort(array,5);
        for(int i=0;i<5;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30

最差时间复杂度 O(n²)  
最优时间复杂度 O(n)  
平均时间复杂度 O(n²)  
最差空间复杂度 O(n) total, O(1) auxiliary

二、插入排序  
插入排序也是一种简单排序方法，算法如下：  
1. 从第一个元素开始，认为该元素已经是排好序的。  
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。  
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。  
4. 重复步骤3，直到已排好序的元素小于或等于新元素。  
5. 在当前位置插入新元素。  
6. 重复步骤2。  
代码实现如下：

#include <iostream>
    using namespace std;
    /*交换函数，作用是交换数组中的两个元素的位置*/
    void swap(int array[],int i,int j)
    {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /*插入排序*/
    void InsertSort(int array[],int n)
    {
        for(int i=1;i<n;i++)
        {
            for(int j=i;j>0;j--)
            {
                if(array[j]>array[j-1])
                    swap(array,j,j-1);
                else
                    break;
            }
        }
    }
    
    int main()
    {
        int array[5]={
       3,1,2,5,4};
        InsertSort(array,5);
        for(int i=0;i<5;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33

最差时间复杂度 O(n²)  
最优时间复杂度 O(n)  
平均时间复杂度 O(n²)  
最差空间复杂度 O(n) total, O(1) auxiliary

三、选择排序  
选择排序的思想如下：  
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。  
2. i=1  
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr\[i\]为最小，逐一比较，若遇到比之小的则交换）  
4. 将上一步找到的最小元素和第i位元素交换。  
5. 如果i=n－1算法结束，否则回到第3步  
代码实现如下：

#include <iostream>
    using namespace std;
    /*交换函数，作用是交换数组中的两个元素的位置*/
    void swap(int array[],int i,int j)
    {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /*选择排序*/
    void SelectionSort(int array[],int n)
    {
        for(int i=0;i<n-1;i++)
        {
            int smallest=i;
            for(int j=i+1;j<n;j++)
            {
                if(array[smallest]>array[j])
                    smallest=j;
            }
            swap(array,i,smallest);
        }
    }
    
    int main()
    {
        int array[5]={
       3,1,2,5,4};
        SelectionSort(array,5);
        for(int i=0;i<5;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33

最差时间复杂度 О(n²)  
最优时间复杂度 О(n²)  
平均时间复杂度 О(n²)  
最差空间复杂度 О(n) total, O(1) auxiliary  
以上三种排序的时间复杂度都是O(n²)。

四、快速排序  
实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。  
快速排序的基本算法是：  
1. 从数列中挑出一个元素，称为 “基准”（pivot），也叫作支点，  
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。  
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。  
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。  
代码实现如下：

#include <iostream>
    using namespace std;
    /*交换函数，作用是交换数组中的两个元素的位置*/
    void swap(int array[],int i,int j)
    {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /*将轴值放到数组的适当的位置*/
    int partition(int array[],int left,int right)
    {
        int mid=(left+right)/2;
        int tmp=array[mid];
        swap(array,mid,right);
        int i=left;
        int j=right;
        while(1)
        {
            /*i指针向右移动，直到找到一个大于轴值的值*/
            while(1)
            {
                /*如果i与j相遇则确定轴值位置，将其返回*/
                if(i==j)
                {
                    array[i]=tmp;
                    return i;
                }
                if(array[i]>tmp)
                {
                    array[j]=array[i];
                    j--;
                    break;
                }
                i++;
            }
            /*j指针向左移动，直到找到一个小于轴值的值*/
            while(1)
            {
                /*如果i与j相遇则确定轴值位置，将其返回*/
                if(i==j)
                {
                    array[j]=tmp;
                    return j;
                }
                if(array[j]<tmp)
                {
                    array[i]=array[j];
                    i++;
                    break;
                }
                j--;
            }
        }
    }
    /*快速排序*/
    void quickSort(int array[],int left,int right)
    {
        if(right<=left)
            return;
        int pivot=partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }
    
    int main()
    {
        int array[8]={
       6,8,7,3,1,2,5,4};
        quickSort(array,0,7);
        for(int i=0;i<8;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44 
       45 
       46 
       47 
       48 
       49 
       50 
       51 
       52 
       53 
       54 
       55 
       56 
       57 
       58 
       59 
       60 
       61 
       62 
       63 
       64 
       65 
       66 
       67 
       68 
       69 
       70 
       71 
       72 
       73 
       74

快速排序的时间复杂度是O(nlogn)，但是最坏情况下复杂度是O(n²)。  
最差时间复杂度 Θ(n²)  
最优时间复杂度 Θ(nlogn)  
平均时间复杂度 Θ(nlogn) comparisons  
最差空间复杂度 根据实现的方式不同而不同。

五.希尔排序（shell sorting）  
增量为2的shell排序的时间代价可以达到θ(n的3/2次方)，有的增量可以达到θ(n的7/6次方)，很接近θ(n)。  
代码实现：

.#include <iostream>
    using namespace std;
    /*交换函数，作用是交换数组中的两个元素的位置*/
    void swap(int array[],int i,int j)
    {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    /*希尔排序*/
    void ShellSort(int array[],int n)
    {
        for(int delta=n/2;delta>0;delta/=2)
        {
            for(int i=0;i<delta;i++)
            {
                for(int j=i+delta;j<n;j+=delta)
                {
                    for(int k=j;k>0;k-=delta)
                    {
                        if(array[k]<array[k-1])
                            swap(array,k,k-1);
                    }
                }
            }
        }
    }
    int main()
    {
        int array[8]={
       6,8,7,3,1,2,5,4};
        ShellSort(array,8);
        for(int i=0;i<8;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36

六.归并排序（merge sorting）  
归并排序的最大时间代价，最小时间代价和平均时间代价均为θ(n\*logn)。归并排序不依赖于原始数组的有序程度。  
代码实现：

#include <iostream>
    using namespace std;
    /*归并过程--将两个有序数组合并成一个有序数组*/
    void merge(int array[],int tempArray[],int left,int right,int middle)
    {
        int i;
        int index1=left;
        int index2=middle+1;
        for(i=left;(index1<=middle)&&(index2<=right);i++)
        {
            if(array[index1]<array[index2])
                tempArray[i]=array[index1++];
            else
                tempArray[i]=array[index2++];
        }
        while(index1<=middle)
            tempArray[i++]=array[index1++];
        while(index2<=right)
            tempArray[i++]=array[index2++];
        for(i=left;i<=right;i++)
            array[i]=tempArray[i];
    }
    /*两路归并排序--array[]为待排数组，tempArray[]为临时数组，left和right分别是数组两端*/
    void mergeSort(int array[],int tempArray[],int left,int right)
    {
        if(left<right)
        {
            int middle=(left+right)/2;
            mergeSort(array,tempArray,left,middle);
            mergeSort(array,tempArray,middle+1,right);
            merge(array,tempArray,left,right,middle);
        }
    }
    int main()
    {
        int array[8]={
       6,8,7,3,1,2,5,4};
        int tempArray[8];
        mergeSort(array,tempArray,0,7);
        for(int i=0;i<8;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
    
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44

七.堆排序（heap sorting）  
堆排序的最大时间代价，最小时间代价和平均时间代价均为θ(n\*logn)。堆排序和归并排序一样，不依赖于原始数组的有序程度。  
代码实现：

#include <iostream>
    #include "MaxHeap.h"
    using namespace std;
    /*最大堆排序函数*/
    void heapSort(int array[],int n)
    {
        MaxHeap max_heap=MaxHeap(array,n);
        /*删除堆的最大值（堆顶），即每次将最大值与数组的最后一个元素交换位置*/
        for(int i=0;i<7;i++)
            max_heap.removeMax();
    }
    int main()
    {
        int array[8]={
       4,3,7,1,2,8,5,6};
        heapSort(array,8);
        for(int i=0;i<8;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20

#include <iostream>
    using namespace std;
    /*最大堆定义*/
    class MaxHeap
    {
    private:
        int size; //最大堆的元素数目
    int * array;  //最大堆数组的首地址指针
    public:
        MaxHeap(int array[],int n); //用已有数组初始化一个最大堆 
             void buildHeap();   //构建最大堆
        void siftDown(int index);  //向下筛选法
        void swap(int index1,int index2);  //交换位置为index1与index2的元素
        void removeMax();  //删除堆顶的最大值--与数组最后一个元素交换位置并重新构建最大堆
        int leftChild(int index);  //返回左孩子的位置
        int rightChild(int index);  //返回右孩子的位置
    };
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17

#include <iostream>
    #include "MaxHeap.h"
    using namespace std;
    /*最大堆成员函数实现*/
    MaxHeap::MaxHeap(int array[],int n)
    {
        this->array=array;
        size=n;
        buildHeap();
    }
    void MaxHeap::buildHeap()
    {
        for(int i=size/2-1;i>=0;i--)
            siftDown(i);
    }
    void MaxHeap::siftDown(int index)
    {
        int max_index=leftChild(index);
        while(max_index<size)
        {
            if(max_index<size-1&&array[rightChild(index)]>array[max_index])
                max_index++;
            if(array[index]>array[max_index])
                break;
            swap(index,max_index);
            index=max_index;
            max_index=leftChild(index);
        }
    }
    void MaxHeap::swap(int index1,int index2)
    {
        int temp=array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }
    void MaxHeap::removeMax()
    {
        swap(0,size-1);
        size--;
        siftDown(0);
    }
    int MaxHeap::leftChild(int index)
    {
        return index*2+1;
    }
    int MaxHeap::rightChild(int index)
    {
        return index*2+2;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44 
       45 
       46 
       47 
       48 
       49

八.桶排序 (Bucket sort)  
1,稳定  
2,常见排序里最快的一种,比快排还要快…大多数情况下  
3,非常耗空间,基本上是空间复杂度最高的一种排序算法  
代码实现：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    void bucket_sort(unsigned * arr,int len)
    {
        unsigned *buckets[10];//指针数组
        unsigned n=1;//用于取整数各位上的值
        int index;//数组下标计数索引
        int indexs[10];//各个桶下标计数索引
        int i,j;//分配动态内存作为桶
        for(i=0; i<10; ++i)
            buckets[i]=(unsigned *)malloc(sizeof(unsigned)*len);
        while(1)
        {
            //计数索引清零
            index=0;
            for(i=0; i<10; ++i)
                indexs[i]=0;//数组至桶
            for(i=0; i<len; ++i)
                buckets[arr[i]/n%10][indexs[arr[i]/n%10]++]=arr[i];//桶至数组
            for(i=0; i<10; ++i)
                for(j=0; j<indexs[i]; ++j)
                    arr[index++]=buckets[i][j];//为取元素的下一位做准备
            n*=10;//判断是否该结束
            for(i=0; arr[i]<n&&i<len; ++i);
            if(i==len) break;
        }//释放动态内存
        for(i=0; i<10; ++i)
            free(buckets[i]);
    }
    void print(unsigned * arr,int len)
    {
        int i=0;
        for(i=0; i<len; ++i)
        {
            printf("%8d",arr[i]);//5个元素一行
            if((i+1)%5==0)
                printf("\n");
        }
    }
    
    int main()
    {
        unsigned array[1002];
        int i=0;//为数组元素随机赋值
        for(i=0; i<1002; ++i)
            array[i]=rand();
        printf("排序前\n");
        print(array,1002);//排序
        bucket_sort(array,1002);
        printf("排序后\n");
        print(array,1002);
        return 0;
    }
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44 
       45 
       46 
       47 
       48 
       49 
       50 
       51 
       52 
       53 
       54 
       55 
       56

平均时间复杂度为线性的O(N+C)，其中C=N\*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高.  
最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)

九.基数排序（radix sorting）  
基数排序的时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。基数排序法是属于稳定性的排序。  
代码实现：

#include <iostream>
    using namespace std;
    /*计算关键字位数的最大值*/
    int KeySize(int array[],int size)
    {
        int key_size=1;
        for(int i=0;i<size;i++)
        {
            int temp=1;
            int n=10;
            while(array[i]/n>0)
            {
                temp++;
                n*=10;
            }
            key_size=(temp>key_size)?temp:key_size;
        }
        return key_size;
    }
    /*基数排序*/
    void RadixSort(int array[],int size)
    {
        int bucket[10][10]={
       0};//定义基数桶
        int order[10]={
       0};//保存每个基数桶之中的元素个数
        int key_size=KeySize(array,size);//计算关键字位数的最大值
        for(int n=1;key_size>0;n*=10,key_size--)
        {
            /*将待排序的元素按照关键值的大小依次放入基数桶之中*/
            for(int i=0;i<size;i++)
            {
                int lsd=(array[i]/n)%10;
                bucket[lsd][order[lsd]]=array[i];
                order[lsd]++;
            }
            /*将基数桶中的元素重新串接起来*/
            int k=0;
            for(i=0;i<10;i++)
            {
                if(order[i]!=0)
                {
                    for(int j=0;j<order[i];j++)
                    {
                        array[k]=bucket[i][j];
                        k++;
                    }
                    order[i]=0;
                }
            }
        }
    }
    
    int main()
    {
        int array[10]={
       73,22,93,43,55,14,28,65,39,81};
        int size=sizeof(array)/sizeof(int);
        RadixSort(array,size);
        for(int i=0;i<size;i++)
            cout<<array[i]<<"  ";
        cout<<endl;
        return 0;
    }原文链接：https://blog.csdn.net/jichangzhen/article/details/52248885