八种排序算法

声明

　　这里使用顺序表的常规定义，对元素类型进行封装，这里暂时使用int类型作为顺序表的元素，可以使用C++的语法将代码重用到任何数据类型，但是需要对数据元素的打印和比较进行重载。另外，所有排序默认为从小到达排列。
　　以下代码可以直接复制到一个cpp文件中进行测试和使用，请包含必要的头文件，比如：stdlib.h、ctime。

顺序表的定义

//顺序表的定义 
#define LIST_INIT_SIZE 100                //顺序表的初始化大小
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<ctime>
typedef int Elem;
typedef struct list{                    //定义顺序表结构体，包含一个数组的地址和数组中有效元素的个数 
    Elem *p;                            //顺序表空间起始地址
    unsigned int len;                   //顺序表中元素个数
}SqList;

顺序表基本函数接口

//基本函数接口的实现
//初始化顺序表
void InitList(SqList &L){                //申请一定大小的数组空间，并把地址给p 
    L.p=(Elem*)malloc(sizeof(Elem)*LIST_INIT_SIZE);
    L.len=0;                             //初始化大小为0 
    if(L.p==NULL){                       //如果分配失败，输出失败提示 
        printf("List init failed. Error: Memory allocation failed.\n");
        exit(EXIT_FAILURE);
    }
}

//在顺序表的下标i处插入新的数据元素,插入成功返回true，否则返回false 
bool ListInsert(SqList &L,unsigned int i,Elem e){
    //如果插入在顺寻表长度范围以外，或者顺序表已满 
    if(i>L.len||L.len==LIST_INIT_SIZE) return false;
    for(int j=L.len;j>i;j--)                //i之后的元素后移 
        L.p[j]=L.p[j-1];
    L.p[i]=e; L.len++;                      //将e插入到下标i处，长度加一 
    return true;         
} 

//遍历输出顺序表的内容
void ListTraverse(SqList L){                //遍历并打印顺序表内容，访问方式可修改 
    for(int i=0;i<L.len;i++){
        if(i) putchar(' ');
        printf("%d",L.p[i]); 
    }
    putchar('\n');    
}

八种排序算法的代码实现

插入排序

//插入排序(从小到大),默认按照递增序列排序。
//空间复杂度O(1),时间复杂度O(n*n)
void InsertSort(SqList &L){
    for(int i=1;i<L.len;i++){               //从下标1开始，将每一个元素插入到前面已经有序的序列中
        int j;
        if(L.p[i]<L.p[i-1]){                //如果当前元素小于前一个元素，则需要进行插入
            Elem temp=L.p[i];               //保留当前需要插入的元素
            for(j=i-1;j>=0&&L.p[j]>temp;j--){
                L.p[j+1]=L.p[j];            //将需要插入的位置之后到i之间的元素都往后移位
            }
            L.p[j+1]=temp;                  //j在-1或在第一个小于等于需要插入的元素位置处停止，故插入在j+1的位置上
        }
    }
}

折半插入排序

//折半插入排序(从小到大)，在寻找插入位置时，使用折半查找，减少比较次数，以增加查找的速度。
//空间复杂度O(1),时间复杂度O(n*n)
void Binary_InsertSort(SqList &L){
    for(int i=1;i<L.len;i++){               //从1开始进行插入排序
                                            //如果当前元素大于等一前一个元素，则不需要插入，进行下一轮循环
        if(L.p[i]>=L.p[i-1]) continue;
        Elem temp=L.p[i];                   //记录需要插入的元素
        int low=0,high=i-1,mid;             //low，hihg，mid为折半的参数
        while(low<=high){                   //边界处应该是low和high相等
            mid=low+(high-low)/2;           //防止相加溢出
            if(L.p[mid]>temp) high=mid-1;   //如果中间值大于要插入的值，则插入位置在左侧
            else              low=mid+1;    //否则插入位置在右侧
        }
        //考虑如果插入元素为10，如果low==high的时候
        //如果该位置是9或者10，循环结束的时候low会增加1，则插入位置是high+1；
        //如果该位置为11，则插入位置应该就是这里，然而循环结束的时候，high会被-1，因此需要+1回到这个位置，即插入位置为high+1
        //综上，插入位置为high+1
        for(int j=i-1;j>=high+1;j--)
            L.p[j+1]=L.p[j];                //将需要插入的位置之后到i之间的元素都往后移位
        L.p[high+1]=temp;                   //在插入元素的位置放置元素
    }
}

希尔排序

//希尔排序(从小到大)，当元素被划分到不同的子表时，可能顺序会法生相对变化，故不稳定。
//空间复杂度O(1),n在某个范围内，空间复杂度为O(n^1.3),最坏时间复杂度O(n*n)
void ShellSort(SqList &L){
    for(int dk=L.len/2;dk>=1;dk/=2){                //dk为步长，初始值为表长，最小值为1，每次减半
        for(int i=dk;i<L.len;i++){                  //对顺序表进行分组，从每组的第一号元素开始进行插入排序，且各组的插入排序可以看作时并发执行的
            if(L.p[i]<L.p[i-dk]){                   //如果当前位置元素小于本组内的上一个元素，则需要插入
                Elem temp=L.p[i];                   //记录待插入的元素
                int j;                              //用于移动元素的工作指针
                for(j=i-dk;j>=0&&L.p[j]>temp;j-=dk) //j从该组上一个元素开始，即将从插入位置到j-dk位置的元素依次后移，其中每次j都要跨越dk的长度
                    L.p[j+dk]=L.p[j];                
                L.p[j+dk]=temp;                     //在插入位置放置需要插入的元素
            }
        }
    }
}

冒泡排序

//冒泡排序(从小到大)
//空间复杂度O(1),时间复杂度O(n*n)
void BubbleSort(SqList &L){
    int n=L.len-1;
    for(int i=0;i<n;i++){                   //冒泡，最多len-1次
        bool flag=false;                    //用于标记本趟冒泡是否发生交换
        for(int j=n;j>=1+i;j--){            //从后往前进行交换,每次确定一个元素位置，所以已有序的部分不用再比较
            if(L.p[j]<L.p[j-1]){            //如果当前位置小于前一个位置的值，则进行交换
                Elem temp=L.p[j];           //交换
                L.p[j]=L.p[j-1];
                L.p[j-1]=temp;
                flag=true;                  //发生交换
            }
        }
        if(flag==false) return;             //如果本趟冒泡未发生交换，则表明已经有序，排序结束
    }
}

快速排序

一般快速排序

//快速排序的划分算法，选取一个枢轴进行划分,将小于枢轴的放在左侧，将大于枢轴的放在右侧
int Partition(SqList &L,int low,int high){      //对L，从low到high之间的部分进行划分
    Elem pivot=L.p[low];                        //选择枢轴
    while(low<high){                            //边界为low==high，此时的位置便是枢轴要安放的位置。
        while(low<high&&L.p[high]>=pivot) high--;//从high侧找到一个小于枢轴的元素，放在低位，也就是枢轴的左侧
        L.p[low]=L.p[high];                     //因为low指针所指的位置上的元素已经被存储为piovt或者被上一次循环移枢轴右侧了，因此直接赋值
        while(low<high&&L.p[low]<=pivot) low++; //从low侧找到一个大于枢轴的元素，放在高位，也就是枢轴的右侧
        L.p[high]=L.p[low];                     //因为high指针所指的位置上的元素已经被移到枢轴左侧了，因此可以直接赋值
    }
    L.p[low]=pivot;                             //当low==high时，便是枢轴所在的位置
    return low;                                 //返回枢轴所在的位置，完成一次划分
}
//快速排序的递归算法
//采用了递归，因此有栈的开销，空间复杂度最好为log(n+1)向上取整，最坏为O(n),平均为O(logn)；时间复杂度最坏为O(n*n)，平均为O(nlogn)
void UseQuickSort(SqList &L,int low,int high){    
    if(low<high){                               //当排序区间不为0时进行排序
        int pos=Partition(L,low,high);          //进行划分
        UseQuickSort(L,low,pos-1);              //左侧递归排序
        UseQuickSort(L,pos+1,high);             //右侧递归排序
    }
}
//快速排序对外函数接口
void QuickSort(SqList &L){
    UseQuickSort(L,0,L.len-1);
}

多线程快速排序

//多线程快速排序
void multiThreadingQuickSort(SqList &L,int low,int high){
    if(low>=high) return;                               //如果区间只有一个元素或者没有元素，那么返回
    int i=low,j=high;
    int pivot = L.p[low];
    while(i<j){                                         //划分
        while(i<j&&L.p[j]>=pivot) j--;
        L.p[i]=L.p[j]; 
        while(i<j&&L.p[i]<=pivot) i++;
        L.p[j]=L.p[i]; 
    }
    L.p[i]=pivot;
    thread t1(multiThreadingQuickSort,ref(L),low,i-1);  //创建两个线程分别处理两侧区间
    thread t2(multiThreadingQuickSort,ref(L),i+1,high);
    t1.join();
    t2.join();
}
void QuickSort(SqList &L){
    multiThreadingQuickSort(L,0,L.len-1);
}

简单选择排序

//简单选择排序，每次从i~len号元素中选取一个最小的与i进行交换
//比较次数与序列状态无关，比较次数为 n(n-1)/2 故时间复杂度为O(n*n)
void SelectSort(SqList &L){
    for(int i=0;i<L.len-1;i++){                 //最多执行n-1次
        int min=i;                              //记录最小元素的下标，初始化为i
        for(int j=i+1;j<L.len;j++)              //从[i,len)中寻找最小元素，并记录下标
            if(L.p[j]<L.p[min]) min=j;
        if(min!=i){                             //如果最小元素不是i处的元素，则于i进行交换
            Elem temp=L.p[min];
            L.p[min]=L.p[i];
            L.p[i]=temp;
        }
    }
}

堆排序

//堆排序，建立大根堆，然后每次将堆顶元素和堆尾巴交换，并调整堆，则最终完成从小到达的排序
//这里的堆序列，下标从0开始
//向下调整的堆的函数，将如果根节点比较小，则向下交换，将[low,high]区间内的元素调整为堆
void AdjustDown(SqList &L,int low, int high){
    int i=low,j=i*2+1;                          //i表示要调整子树的根结点，j表示i的左孩子
    while(j<=high){                             //如果j不超过数组的j限制，说明左孩子存在
        if(j+1<=high&&L.p[j+1]>L.p[j])          //如果右孩子存在，并且右孩子比左孩子大，用j记录右孩子
            j++;                                //这保证了i和孩子交换以后保持大根状态，即将i和左右孩子中较大的那个交换
        if(L.p[j]>L.p[i]){                      //如果根比较小，需要向下调整
            Elem temp=L.p[i];                   //将i和两个孩子中较大的那个交换
            L.p[i]=L.p[j];
            L.p[j]=temp;
            i=j; j=2*i+1;                       //将i修改为与调整点，即下标j，然后将j改为i的左孩子，开始下一轮调整
        }
        else break;                             //如果不需要向下调整了，则调整完毕，结束循环
    }
}
//建立大根堆的过程
void BuildMaxHeap(SqList &L){                
    for(int i=L.len/2-1;i>=0;i--)             //从最有一个非叶子结点开始一次往上，对每一个结点做向下调整
        AdjustDown(L,i,L.len-1);                //将从[i,len-1]区间内调整成为大根堆
}
//堆排序算法，每次将堆尾部的元素和堆顶进行交换，再将上部分剩下的堆进行调整形成大根堆
//因此可以从大到小逆序的填充数组，形成从小到大的排序
void HeapSort(SqList &L){                    
    BuildMaxHeap(L);                            //建立大根堆
    for(int i=L.len-1;i>=0;i--){                //从堆尾部开始，依次弹出堆顶放在堆尾上
        Elem temp=L.p[0];                       //每次将堆尾和堆顶进行交换
        L.p[0]=L.p[i];
        L.p[i]=temp;
        AdjustDown(L,0,i-1);                    //调整上部分的堆使其保持大根堆的形态
    }
}

归并排序

　　归并排序可以通过递归方式实现，也可以通过非递归方式实现，这里暂时给出递归实现的代码。

归并排序的递归实现

//将顺序表L中从left~mid-1和mid~right之间的元素归并成一个有序序列，tempL为辅助数组，由调用函数申请并传入
void Merge(SqList &L,SqList &tempL,int left,int mid,int right){
    int i=left,j=mid;                           //i为左半段的指针，j为右半段的指针
    int tmp=left;                               //tmp为辅助数组的指针
    while(i<=mid-1&&j<=right){                  //将两段从小到大进行归并
        if(L.p[i]<=L.p[j])
            tempL.p[tmp++]=L.p[i++];
        else
            tempL.p[tmp++]=L.p[j++];
    }
    while(i<=mid-1)    tempL.p[tmp++]=L.p[i++]; //如果有某一段仍有剩余，归并入临时数组中
    while(j<=right)    tempL.p[tmp++]=L.p[j++];
    for(tmp=left;tmp<=right;tmp++)              //将归并好的有序序列放回到原始顺序表中
        L.p[tmp]=tempL.p[tmp];
}
//核心递归排序函数
void Msort(SqList &L,SqList &tempL,int left,int right){
    if(left<right){                             //如果归并段大于1进行归并
        int mid=left+(right-left)/2;            //取中间进行分段,防止相加溢出
        Msort(L,tempL,left,mid);                //对左边进行归并
        Msort(L,tempL,mid+1,right);             //对右边进行归并
        Merge(L,tempL,left,mid+1,right);        //合并两个有序段
    }
}
//归并排序的接口函数
void MergeSort(SqList &L){                    
    SqList tempL;                               //构建临时的辅助顺序表
    tempL.p=(Elem*)malloc(L.len*sizeof(Elem));  //为临时数组开辟空间，这里没有用
    if(tempL.p!=NULL){                          //如果申请空间成功
        Msort(L,tempL,0,L.len-1);               //归并
        free(tempL.p);                          //释放空间
    }
    else exit(EXIT_FAILURE);                    //如果申请失败则退出
}

归并排序的非递归实现

验证

用于验证排序有效性的main函数

//测试使用的主函数
int main(void){
    int size=30;                                //顺序表中元素的个数
    Elem temp;
    SqList L[8];                                //创建8个相同的顺序表
    for(int i=0;i<8;i++)    InitList(L[i]);     //分别初始化
    srand((int)time(NULL));                     //随机数的种子
    for(int i=0;i<size;i++){
        temp=rand()%100;                        //产生100以内的随机数
        for(int j=0;j<8;j++)    ListInsert(L[j],0,temp);
    }
    printf("----------------------------------------------------------------------\n");
    printf("八种排序算法的验证如下：\n");
    printf("原始数组内容为：\n");

    ListTraverse(L[0]);
    printf("----------------------------------------------------------------------\n");
    printf("插入排序结果如下：\n");
    InsertSort(L[0]);
    ListTraverse(L[0]);

    printf("----------------------------------------------------------------------\n");
    printf("折半插入排序结果如下：\n");
    Binary_InsertSort(L[1]);
    ListTraverse(L[1]);

    printf("----------------------------------------------------------------------\n");
    printf("希尔排序结果如下：\n");
    ShellSort(L[2]);
    ListTraverse(L[2]);

    printf("----------------------------------------------------------------------\n");
    printf("冒泡排序结果如下：\n");
    BubbleSort(L[3]);
    ListTraverse(L[3]);

    printf("----------------------------------------------------------------------\n");
    printf("快速排序结果如下：\n");
    QuickSort(L[4]);
    ListTraverse(L[4]);

    printf("----------------------------------------------------------------------\n");
    printf("简单选择排序结果如下：\n");
    SelectSort(L[5]);
    ListTraverse(L[5]);

    printf("----------------------------------------------------------------------\n");
    printf("堆排序结果如下：\n");
    HeapSort(L[6]);
    ListTraverse(L[6]);

    printf("----------------------------------------------------------------------\n");
    printf("归并排序结果如下：\n");
    MergeSort(L[7]);
    ListTraverse(L[7]);

    printf("----------------------------------------------------------------------\n");

    return 0;
}

某次测试的结果

----------------------------------------------------------------------
八种排序算法的验证如下：
原始数组内容为：
9 97 61 67 23 29 40 79 53 10 74 44 42 86 79 4 62 42 52 98 64 37 44 7 27 47 23 18 88 82
----------------------------------------------------------------------
插入排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
折半插入排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
希尔排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
冒泡排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
快速排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
简单选择排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
堆排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------
归并排序结果如下：
4 7 9 10 18 23 23 27 29 37 40 42 42 44 44 47 52 53 61 62 64 67 74 79 79 82 86 88 97 98
----------------------------------------------------------------------

排序算法对比

　　排序算法的时间复杂度、空间复杂度和稳定性对比如下所示：

排序算法	最坏时间复杂度	最好时间复杂度	平均时间复杂度	空间复杂度	稳定性
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序			O(n^1.3)	O(1)	不稳定
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
快速排序	O(n^2)	O(nlogn)	O(nlogn)	O(nlogn)	不稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	稳定