使序列成为一个按关键字有序的序列,这样的操作称为排序。

排序问题中,我们的输入是一个记录的集合,输出也是一个记录集合,所以可以把排序看成是线性表的一种操作。

排序的稳定性

一个记录序列可以有多个关键字,如id值和姓名首字母都可以作为关键字,主要看我们如何规定。

而排序也不仅是针对主关键字,也可以针对多个次关键字,这样就有可能造成按不同关键字排序的结果可能不唯一,由此给出稳定性和不稳定性排序的定义。

若按不同关键字排序结果相同,则称排序方法稳定,否则不稳定。

排序用的结构与函数

后面的排序(除了桶排序)都是使用下面定义的这两个结构。

1.提供一个用于排序的顺序表结构

#define MAXSIZE 10
typedef struct
{
    int r[MAXSIZE+1];   //用于存储要排序的数组,r[0]可用作哨兵或临时变量(在直接插入排序中用到)
    int length;         //记录顺序表长度
}SqList;

2.排序中最常见的操作是交换数组中的两个元素,我们将它写成一个函数方便使用。

void swap(SqList *L, int i, int j) {
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

一、最快捷的排序——桶排序

桶排序的思想是:把要排序的数按下标存进一个数组里(也就是说,把1存进a[1],3存进a[3],100存进a[100]里),然后再遍历数组,依次打印出来。

由于桶排序不常用,也不是我们学习的重点,这里只介绍最简单的桶排序,真正的桶排序比这个要复杂不少。

代码:

//桶排序
int main() {
    int r[11] = {0, 1, 5, 9, 8, 7, 6, 3, 12, 2, 4};
    int a[100];
    for (int i = 0; i < 100; i++)
        a[i] = 0;                         //将a[100]数组初始化为0
    for (int i = 1; i <= 11; i++) {
        a[r[i]] += 1;                     //r[i]的值在a[100]数组对应下标的元素+1
    }
    for (int i = 0; i < 100; i++)
        for (int j = 1; j <= a[i]; j++)  //将a[100]中大于0的数的下标打印出来
            printf("%d ", i);            //a[100]元素值是多少,就打印多少次
}
  • 平均时间复杂度:O(n + k)
  • 最佳时间复杂度:O(n + k)
  • 最差时间复杂度:O(n²)
  • 空间复杂度:O(n * k)

桶排序的十分快捷,在数字不重复的情况下,时间复杂度仅仅为O(n)!

但桶排序最大的不足是:占用了太多的空间,这么大的空间浪费在程序设计中是不被允许的,所以我们一般编程过程中是不会用到桶排序。

二、平均时间复杂度为O(n²)的排序

时间复杂度为O(n)的排序有:最简单排序,冒泡排序,简单选择排序,直接插入排序。

1、最简单排序

说起排序,最容易想到和编写代码的,就是把先把第一个数和后面比较,大的话交换,找到最小的数;第二个数和后面的比较,大的话交换,找到第二小的数......

这就是最简单排序的思想

//最简单排序
void EasySort(SqList *L) {
    for (int i = 1; i < L->length; i++)     //因为定义时r[0]不用于放有用值,所以从1开始循环
        for (int j = i + 1; j < L->length; ++j)
            if (L->r[i] > L->r[j])
                swap(L, i, j);
}

这个算法,第一次循环时找到了所需的最小值,但不断交换时却把第二小的值排在了很后面。以至于第二次循环时又要排序和交换很多次,才能找到这个第二小的值。

比如:排序 923567148,第一次循环:923567147 → 293567148 → 193567248 ,

可以看到,本来第二小的2排在第二位,第一次循环排序完,2反而拍到了第七位,第二次循环要交换五次才能找到2。

这样的算法效率非常低下。

2、冒泡排序

冒泡排序是对最简单排序的一点优化,它的思想跟最简单排序差不多。

区别是冒泡排序是当前数和它后一位数比较,如果小的话就交换。这样排序的好处是避免了最简单排序那样,每次排序把第二小的数交换到了后面。

//冒泡排序
void BubbleSort(SqList * L)
{
    for (int i = 1; i < L->length; ++i)
        for (int j = L->length-1; j >= 1; --j)  //注:这里是从后往前循环,这样才能保证最小的数从后面不断交换被推到前面
            if(L->r[j+1] < L->r[j])
                swap(L,j,j+1);
}

值得注意的是:如果i从前到后循环,则j需要从后往前循环(把最小数推到最前面),因为第二次i=2,从第二位开始,第一位已经不参与排序,所以必须保证这个时候第一位是最小值,而只有j从后向前,才能把最小值推到第一位。

3、冒泡排序优化

加入要排序 21345,第一趟循环就排序好了,我们知道继续比较下去没有意义了,但计算机不知道,程序仍会继续进行第二趟,第三趟....循环比较。

在某一趟循环若相邻的数前面都小于后面,说明已经排序好了,不需要继续循环。因此冒泡排序优化,就是给冒泡排序添加一个在适当时候终止的命令。

//冒泡排序优化
void BubbleSort1(SqList *L) {
    bool flag;          //加一个布尔值用于判断终止循环
    for (int i = 1; i < L->length; ++i) {
        flag = true;    //每次循环flag初始化为true
        for (int j = L->length - 1; j >= 1; --j)
            if (L->r[j + 1] < L->r[j]) {
                swap(L, j, j + 1);
                flag = false;    //一旦有交换,本次循环flag为false
            }
        if (flag)
            return;     //如果某次循环没有交换,则flag为true,则终止算法
    }
}

4、简单选择排序

简单选择排序相当于最简单排序的进一步优化。

最简单排序的思想是 每次循环不断把在后面的小的数交换到前面。但交换要调用函数swap,多次调用很耗时。

简单选择排序的思想是 在每次循环比较中记下最小数的下标,循环结束后再进行交换,这样每次循环都只要交换一次。

void SelectSort(SqList * L)
{
    for (int i = 1; i < L->length; ++i) {
        int min = i ;        //定义一个变量min来记录最小值的下标
        for (int j = i+1; j <= L->length; j++) 
            if(L->r[min] > L->r[j])
                min = j;    //用记录下标的方式来代替交换
        if(i!=min)
            swap(L,i,min);  //每次循环结束后再进行交换
    }
}

5、直接插入排序

我们之前把r[0]定义为哨兵,就是在这里派上用场。

前面的排序方法都是用交换的思想,而直接插入排序,是像扑克牌一样,先把这个数抽出来,找到合适的位置再插进去。如图:

(整个过程没有涉及到交换,不用调用swap函数)

void InsertSort(SqList *L) {
    int j;
    for (int i = 1; i <= L->length; ++i)
        if (L->r[i] < L->r[i - 1]) {        //找到一个数a,a小于它的前一位数b
            L->r[0] = L->r[i];              //r[0]是哨兵,将a赋值给哨兵
            for (j = i-1; L->r[j] > L->r[0]; j--)   //从b的前一位数往前找,找到合适的插入位置:j
                L->r[j + 1] = L->r[j];      //将b前一位数都往后移一位数,这样b就被覆盖了,避免插入后数组中有2个b
            L->r[j + 1] = L->r[0];          //在j后面插入
        }
}

总结:

虽然这几种排序的时间复杂度都是O(n²),但是总体从调用函数,平均比较、移动次数等来看,可以得出:性能方面,直接插入排序 > 简单选择排序 >冒泡排序 > 最简单排序。

三、 平均时间复杂度<O(n²)的排序

时间复杂度<O(n²)的排序有:希尔排序、堆排序、归并排序、快速排序

1、希尔排序

希尔排序是直接插入排序的升级版

原理:

它的原理是:将一组数分割成几个子序列,然后在这些子序列内部进行直接插入排序,这时子序列有序,子序列合并的全部序列基本有序(像213647589这样,小的基本都在前,大的基本都在后,叫基本有序)。然后再对全体记录进行一次直接插入排序,这样整个序列就排好顺序了。

我们分割记录的目的是:减少待排序的记录个数,并使整个序列向整体有序发展。而主要的问题在于如何选取子序列,排完才能使全部序列基本有序。比如,要排序 915837462 ,若直接将其分成三组:915,837,462;子序列排序排序:159,378,462;子序列合并后:159378462,可以看到,9在前面,2在后面,根本算不上基本有序,这样排序就没有意义。因此,我们采取的是跳跃分割的策略:将相距某个增量的记录组成子序列先进行交换。这样才能保证子序列排序后合并的结果是基本有序。

例如:我们要排序 915837462,假设先取增量为4,也就是说第1位和第5位比较,第2位和第6位比较,......,循环一次后,序列为:314627589,然后再假设增量为2,第二次循环后得到序列:312647589,再假设增量为1,第三次循环后得到序列:123456789.

增量序列:

这里有个问题是,增量该取多少,目前还是一个数学难题,增量不同导致时间复杂度也不同,增量取得不好,希尔排序效率甚至比直接插入排序还要低,但目前还没有人找到一种最好的增量序列。

最简单的,我们可以取序列为$D_M=[\frac N2],D_k=[\frac {D_{k+1}}2]$,此时的最坏的时间复杂度也为O(n^2),但总体效率不会比直接插入排序差。

还有很多大佬给出这些增量序列,比如:Hibbard增量序列($D_k=2^k-1$,如:1,3,7,15,31...),最坏的时间复杂度为O($N^{3/2}$),平均时间复杂度为($N^{5/4}$)。还有Knuth增量序列、Sedgewick增量序列等等,就不一 一介绍了。

需要注意的是,增量序列最后一个增量值必须等于1.

代码:

void ShellSort(SqList *L) {
    int increment = L->length;         //变量increment记录增量
    int i, j;
    do {
        increment = increment / 2 ;    //这里可以改成想要的增量序列,先假设增量序列为最简单的[N/2]
        for (i = increment + 1; i <= L->length; i++) {
            if (L->r[i] < L->r[i - increment]) {
                L->r[0] = L->r[i];
                for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
                    L->r[j + increment] = L->r[j];
                L->r[j + increment] = L->r[0];
            }
        }
    } while (increment > 1);
}

2、堆排序

堆排序是对简单选择排序的改进。简单选择排序在对第一次循环排序n个数时,需比较n-1次,但可惜比较的记录没有保存下来,在后面的循环时,有很多个比较前面循环已经做过了,后面循环又重复了这些操作。

要了解堆排序,首先要知道什么是堆,堆是一种特殊的完全二叉树,它有以下两类:

  • 大顶堆(大根堆):每个结点的值都大于或等于它的左右孩子结点的值
  • 小顶堆(小根堆):每个结点的值都小于或等于它的左右孩子结点的值
大顶堆
小顶堆

以下我们都用大顶堆进行介绍和应用。

由大顶堆性质:根结点一定是所有结点的最大值。只要每次取出根结点元素,然后继续调整剩余元素成一个堆,继续取出根结点...以此类推,就能完成排序。

因此,推排序也就分解成了两个问题:

  1. 如何把一个无序序列构建成一个堆
  2. 取出根结点后,如何调整剩下的元素成为一个新的堆。

调整序列为一个大顶堆

代码:

//构造大顶堆
//L->r为传入的序列,m为序列长度length,s应由 [length/2]到1 或 1到[length/2]
void HeapAdjust(SqList *L, int s, int m)  //s为所有子树根结点的序号,由前面二叉树的知识,我们可以知道,完全二叉树根序号为1,2,4,8..,[length/2]
{
    int temp = L->r[s];                       //s为子树根结点,temp用于记录子树根结点的值,便于后续插入
    int j;
    for (j = 2 * s; j <= m; j *= 2)           //遍历所有左孩子结点
    {
        if (j < m && L->r[j] < L->r[j + 1])   //如果左子树小于右子树,将下标j指向右子树
            ++j;                               
        if (temp >= L->r[j])                  //根结点大于左右子树
            break;
        L->r[s] = L->r[j];                    //根结点没有大于左右子树,则子树的数赋值给根结点,继续循环。
        s = j;
    }
    L->r[s] = temp;    //插入
}

比如:我们传入的L->r为{10000,50,10,90,30,70,40,80,60,20},r[0]为哨兵位,可以是任意值,m=9,s为4递减到1。

函数内第一行:temp=L->r[4]=30

函数内第三到十一行:循环遍历s根结点的孩子结点,为什么从2*s开始?因为二叉树的性质,序号2*s是根结点的左子树,右子树序号为2*s + 1 。根结点的孩子序号肯定也是以2的倍数增加,因此循环条件为j *= 2 。当前第一次循环j=2*s=8。

函数内第五到第六行:满足判断条件说明左孩子小于右孩子。我们的目标是找到孩子子树最大值,所以要让j指向右孩子的序号,j++。当前L->r[8]=60,L->r[9]=20,不满足左孩子小于右孩子,j不变。

函数内第七到第八行: 根结点大于左右子树,找到合适位置了,跳出循环,当前不满足条件,不执行break,继续往下

函数内第九到第十行: 根结点没有大于左右子树,则根结点和子树互换位置 ,继续循环。当前r[j]=r[8]=60,赋值后,r[4]=r[8]=60,s=j=8。结束第一次循环

进行第二次循环:j=16,超过m的范围了,for条件结束,跳出循环。r[8]=temp=30

第一次s=4的这次调用,其是把最后一个根结点和它的右子树互换,使它满足大顶堆的定义,根结点大于左右子树。

之后开始第二次调用 HeapAdjust 函数,传入s=3......直到从下到上每个根结点都经历了一遍,整个序列就都满足大顶堆了。其实逻辑上很简单,也就是每次三个数的比较,逐层判断根结点值是不是最大的,不是的话就和值最大的孩子结点交换,使其最大。用递归也更好实现,但是为了提高效率, 还是采用非递归的方法。

输出顶堆元素后,调整剩余元素为新的大顶堆,循环完成排序

因为每次循环堆顶元素是最大值,所以每次循环结束把堆顶元素和最后一个结点交换,然后用i-1个元素进行排序(排除不进行堆调整排序的那1个元素是交换过去的最大值元素)。

比如上面的{10000,50,10,90,30,70,40,80,60,20},第一次调整成堆后,堆顶元素是90,最后一个结点元素是20,交换两个元素,最后一个结点元素成了90,用剩余的8个元素进行堆调整,再把堆顶70和最后一个结点元素20交换.....直至i=2时,所有元素都调整完毕,完成排序。(不用到i=1是因为i=2时调用HeapAdjust函数,传入的是i-1=1,也就是说i=2时,已经只有最后一个元素没调整了)。

代码:

void HeapSort(SqList *L) {
    int i;
    for (i = L->length / 2; i > 0; i--) //把L->rua调整成一个大顶堆
        HeapAdjust(L, i, L->length);
    for (i = L->length; i > 1; i--) {
        swap(L, 1, i);                  //将根结点和最后一个结点交换
        HeapAdjust(L, 1, i - 1);        //将剩余i-1个元素重新调整成大顶堆。
    }
}

算法分析

堆排序的运行时间主要消耗在初始构建堆以及重建堆上。

构建堆的时间复杂度为O(n),重建堆的时间复杂度为O($n\log_2n$),因此总的时间复杂度为O($n\log_2n$),总体效率很高。

但实际中初始构建堆时所需移动的次数比较多,如果序列简单,可能效率不如时间复杂度为O(n²)的算法。比如排序13245这个序列,构建堆也是个不小的工作量。因此,堆排序并不适用于排序元素个数较少的情况

3、归并排序

归并排序利用的也是完全二叉树,相比于堆排序,它的思想更为简单。

它的原理是:先将n个序列分为n组(此时每组1个元素),然后两两比较,并配对形成n/2(n为偶数时)个序列,再继续把n/2组元素两两比较,形成n/4个序列......直到n=1完成排序,整个过程像一个倒的完全二叉树,如图:

因此排序问题也分为两部分:如何把两个有序序列结合同时整体有序,递归调用实现归并排序。

两个有序序列结合同时有序

简单的思路是:构建一个新的空数组,同时遍历并比较两个序列的值,把小的值加到这个数组里。最后肯定有一个序列没遍历完,再把这个序列的剩余值直接加到这个数组里。

代码:

//将有序的两个序列SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Merge(int SR[], int TR[], int i, int m, int n) {
    int j = m + 1;
    int k = i;              //记录当前要插入TR数组哪个位置的下标
    while (i <= m && j <= n) {
        if (SR[i] < SR[j]) {
            TR[k] = SR[i];
            i++;
            k++;
        } else {
            TR[k] = SR[j];
            j++;
            k++;
        }
    }
    if (i <= m)             //序列SR[i..m]没遍历完,剩余值直接复制到TR
    {
        for (; i <= m; i++, k++)
            TR[k] = SR[i];
    }
    if (j <= n) {           //序列SR[m+1..n]没遍历完,剩余值直接复制到TR
        for (; j <= n; j++, k++)
            TR[k] = SR[j];
    }
}

递归实现归并排序

代码:

//因为用到递归,每次传入的参数不同,所以要单独写成一个函数
//目的是最后使TR1数组有序
void MSort(int SR[], int TR1[], int i, int n) {
    int m;
    int TR2[MAXSIZE + 1];         //新建一个数组,用来暂时存放递归后的序列
    if (i == n)                   //递归结束的标志:首元素下标i和尾元素下标n相等,首尾重合
        TR1[i] = SR[i];
    else {
        m = (i + n) / 2;          //m是数组长度的平均数
(取整),用来把一个序列从中间分割成两个
        MSort(SR, TR2, i, m);     //递归将SR[i..m]归并为有序的TR2[i..m]
        MSort(SR, TR2, m + 1, n); //递归将SR[m+1..n]归并为有序的TR2[m+1..n]
        Merge(TR2, TR1, i,m, n);  //调用函数,将TR2[i..m]和TR2[m+1..n]归并到TR1[i..n]
    }
}


void MergeSort(SqList *L) {
    MSort(L->r, L->r, 1, L->length);
}

图解递归过程:

归并排序分析:

归并排序最好、最坏、平均时间复杂度都为O($n\log_2n$),空间复杂度为O(n+$\log_2n$)。总体是一个比较占用空间,但是效率很高且稳定的算法。

当然,归并排序还能优化成非递归的算法,避免了递归深度为$\log_2n$的栈空间,空间复杂度降为O(n),时间复杂度也有一定的下降。具体算法实现不做要求,在这里也就不过多介绍了。

4、快速排序

快速排序算法,被列为20世纪十大算法之一,它是冒泡排序的升级版。冒泡排序通过相邻两个数不断比较和交换,把大的数往后推(或把小的数往前推),而快速排序增大了比较和移动的距离,将大的数从前面直接移到后面,从而减少了总比较次数和交换次数。

它的原理是:通过一趟排序将序列分割成独立的两部分(高子表和低子表),其中低子表的数均比高子表的数小,然后分别堆这两部分继续排序并分割(递归),最后整体即为有序。

而这样做的关键是:我们要选取一个数,把它放到适当位置,使它左边的值都比它小,右边的值都比它大,这个数我们成为枢轴。(后续代码中,我们用函数Partition()来找出这个位置)。

所以问题就分为两部分了。先粗略排序并找出枢轴位置,对左右两部分递归。为了方便理解,下面的代码用函数调用的形式给出。

粗略排序并找出枢轴位置

整个大致为:以第一个元素作为枢轴值,然后从两端交替向中间遍历,先从右向左遍历,如果有一个值比枢轴小,交换枢轴和该数 ,然后从左往右遍历,如果有一个值比枢轴大,交换枢轴和该数......循环直到所有数都扫描到了,此时,枢轴左端的数一定以枢轴小,右端的数一定比枢轴大。

代码:

//快速排序的关键——枢轴值
//low和high为要排序的第一个元素和最后一个元素位置,传入1和L->length即可
int Partition(SqList *L,int low ,int high){
    int pivotkey = L->r[low];                     //用第一个元素作为枢轴值
    while(low < high)                             //从表的两端交替向中间扫描
    {
        while(low<high && L->r[high] >= pivotkey) //从右向左扫描,直到直到一个值小于枢轴pivotkey
            high--;
        swap(L,low,high);                         //将比枢轴小的值和枢轴交换位置
        while(low<high && L->r[low] <= pivotkey)  //从左向右扫描,直到一个值大于枢轴pivotkey
            low++;
        swap(L,low,high);
    }
    return low;
}

图解:

递归调用完成排序

代码:

//因为要用递归,每次递归传入的参数不同,所以把该过程单独写一个函数。
void QSort(SqList *L, int low, int high) {
    int pivot;
    if (low < high) {                     //当low=high时,低子表或高子表只有一个元素,这一部分排序完成。
        pivot = Partition(L, low, high);  //调用函数,粗略排序并返回枢轴位置
        QSort(L, low, pivot - 1);         //递归,对低子表排序
        QSort(L, pivot + 1, high);        //递归,对高子表排序
    } 
}


//调用QSort对L->r完成快速排序
void QuickSort(SqList *L) {
    QSort(L, 1, L->length);
}

快速排序的优化

上面最基本的快速排序还有不少可以优化的地方,比如:优化枢轴的选取(三数取中法和九数取中法),优化枢轴选取过程中不必要的交换(类似简单选择排序,用下标记录的方法来代替调用swap函数),还有对递归的优化 ........ 优化的方法很多,我们掌握最基本的快速排序即可,这里就不过多介绍了。

快速排序的时间复杂度为O($n\log_2n$),空间复杂度为O($\log_2n$)。

四、所有排序算法的比较

上面的排序算法可以分为两类:

  • 简单算法:冒泡、简单选择、直接插入
  • 改进算法:希尔、堆、归并、快速

从平均时间复杂度来看,其他的改进算法都优于希尔排序,所有改进算法都远胜于简单算法。

从最好情况看,反而冒泡和直接插入排序要优于改进算法。也就是说,如果本来的序列就基本有序,不应该考虑用改进算法。

从最坏情况看,堆排序和归并排序又优于快速排序和其他排序。

从空间复杂度看,如果不想占用过多空间,就不应该选择归并排序和快速排序。

五、所有排序全部代码

#include "stdio.h"

#define MAXSIZE 10
typedef struct {
    int r[MAXSIZE + 1];   //用于存储要排序的数组,r[0]可用作哨兵或临时变量(在直接插入排序中用到)
    int length;         //记录顺序表长度
} SqList;

void swap(SqList *L, int i, int j) {
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}


//最简单排序
void EasySort(SqList *L) {
    for (int i = 1; i < L->length; i++)     //因为定义时r[0]不用于放有用值,所以从1开始循环
        for (int j = i + 1; j < L->length; ++j)
            if (L->r[i] > L->r[j])
                swap(L, i, j);
}

//冒泡排序
void BubbleSort(SqList *L) {
    for (int i = 1; i < L->length; ++i)
        for (int j = L->length - 1; j >= 1; --j)  //注:这里是从后往前循环,这样才能保证最小的数从后面不断交换被推到前面
            if (L->r[j + 1] < L->r[j])
                swap(L, j, j + 1);
}

//冒泡排序优化
void BubbleSort1(SqList *L) {
    bool flag;          //加一个布尔值用于判断终止循环
    for (int i = 1; i < L->length; ++i) {
        flag = true;    //每次循环flag初始化为true
        for (int j = L->length - 1; j >= 1; --j)
            if (L->r[j + 1] < L->r[j]) {
                swap(L, j, j + 1);
                flag = false;    //一旦有交换,本次循环flag为false
            }
        if (flag)
            return;     //如果某次循环没有交换,则flag为true,则终止算法
    }
}

//简单选择排序
void SelectSort(SqList *L) {
    for (int i = 1; i < L->length; ++i) {
        int min = i; //定义一个变量min来记录最小值的下标
        for (int j = i + 1; j <= L->length; j++)
            if (L->r[min] > L->r[j])
                min = j;    //用记录下标的方式来代替交换
        if (i != min)
            swap(L, i, min);  //每次循环结束后再进行交换
    }
}

//直接插入排序
void InsertSort(SqList *L) {
    int j;
    for (int i = 1; i <= L->length; ++i)
        if (L->r[i] < L->r[i - 1]) {        //找到一个数a,a小于它的前一位数b
            L->r[0] = L->r[i];              //r[0]是哨兵,将a赋值给哨兵
            for (j = i - 1; L->r[j] > L->r[0]; j--)   //从b的前一位数往前找,找到合适的插入位置:j
                L->r[j + 1] = L->r[j];      //将b前一位数都往后移一位数,这样b就被覆盖了,避免插入后数组中有2个b
            L->r[j + 1] = L->r[0];          //在j后面插入
        }
}

//希尔排序
void ShellSort(SqList *L) {
    int increment = L->length;        //变量increment记录增量
    int i, j;
    do {
        increment = increment / 2;    //这里可以改成想要的增量序列,先假设增量序列为最简单的[N/2]
        for (i = increment + 1; i <= L->length; i++) {
            if (L->r[i] < L->r[i - increment]) {
                L->r[0] = L->r[i];
                for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment)
                    L->r[j + increment] = L->r[j];
                L->r[j + increment] = L->r[0];
            }
        }
    } while (increment > 1);
}



//堆排序
//构造大顶堆
//传入的m为序列长度length,s应由 [length/2]递减到1
void HeapAdjust(SqList *L, int s, int m)  //L->r为传入的序列,m为序列长度,s为所有子树根结点的序号,由前面二叉树的知识,我们可以知道,完全二叉树根序号为1,2,...,[length/2]
{  
    int temp = L->r[s];                   //s为子树根结点,temp用于记录子树根结点的值,便于后续插入
    int j;
    for (j = 2 * s; j <= m; j *= 2)       //沿序号大的孩子结点向下筛选
    {
        if (j < m && L->r[j] < L->r[j + 1])
            ++j;
        if (temp >= L->r[j])
            break;
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp;    //插入
}


//调用完成堆排序
void HeapSort(SqList *L) {
    int i;
    for (i = L->length / 2; i > 0; i--)        //把L->r调整成一个大顶堆
        HeapAdjust(L, i, L->length);
    for (i = L->length; i > 1; i--) {
        swap(L, 1, i);                         //将根结点和最后一个结点交换
        HeapAdjust(L, 1, i - 1);               //将剩余i-1个元素重新调整成大顶堆
        //为什么传入的是1?因为相比于原来调整好的堆,只是堆顶结点变了,只要调整堆顶结点即可
    }
}



//快速排序
//快速排序的关键——枢轴值和位置
int Partition(SqList *L, int low, int high) {
    int pivotkey = L->r[low];                         //用第一个元素作为枢轴值
    while (low < high)                                //从表的两端交替向中间扫描
    {
        while (low < high && L->r[high] >= pivotkey)  //从右向左扫描,直到直到一个值小于枢轴pivotkey
            high--;
        swap(L, low, high);                           //将比枢轴小的值和枢轴交换位置
        while (low < high && L->r[low] <= pivotkey)   //从左向右扫描,直到一个值大于枢轴pivotkey
            low++;
        swap(L, low, high);
    }
    return low;
}

//因为要用递归,每次递归传入的参数不同,所以把该过程单独写一个函数。
void QSort(SqList *L, int low, int high) {
    int pivot;
    if (low < high) {
        pivot = Partition(L, low, high);   //调用函数,粗略排序并返回枢轴位置
        QSort(L, low, pivot - 1);          //递归,对低子表排序
        QSort(L, pivot + 1, high);         //递归,对高子表排序
    }
}

//调用QSort对L->r完成快速排序
void QuickSort(SqList *L) {
    QSort(L, 1, L->length);
}

//归并排序
//将有序的两个序列SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
void Merge(int SR[], int TR[], int i, int m, int n) {
    int j = m + 1;
    int k = i;              //记录当前要插入TR数组哪个位置的下标
    while (i <= m && j <= n) {
        if (SR[i] < SR[j]) {
            TR[k] = SR[i];
            i++;
            k++;
        } else {
            TR[k] = SR[j];
            j++;
            k++;
        }
    }
    if (i <= m)             //序列SR[i..m]没遍历完,剩余值直接复制到TR
    {
        for (; i <= m; i++, k++)
            TR[k] = SR[i];
    }
    if (j <= n) {           //序列SR[m+1..n]没遍历完,剩余值直接复制到TR
        for (; j <= n; j++, k++)
            TR[k] = SR[j];
    }
}


//因为用到递归,每次传入的参数不同,所以要单独写成一个函数
//目的是最后使TR1数组有序
void MSort(int SR[], int TR1[], int i, int n) {
    int m;
    int TR2[MAXSIZE + 1];          //新建一个数组,用来暂时存放递归后的序列
    if (i == n)                    //递归结束的标志:首元素下标i和尾元素下标n相等
        TR1[i] = SR[i];
    else {
        m = (i + n) / 2;           //m是数组长度的平均数(取整),用来把一个序列从中间分割成两个
        MSort(SR, TR2, i, m);      //递归将SR[i..m]归并为有序的TR2[i..m]
        MSort(SR, TR2, m + 1, n);  //递归将SR[m+1..n]归并为有序的TR2[m+1..n]
        Merge(TR2, TR1, i, m, n);  //调用函数,将TR2[i..m]和TR2[m+1..n]归并到TR1[i..n]
    }
}


//调用完成归并排序
void MergeSort(SqList *L) {
    MSort(L->r, L->r, 1, L->length);
}

//主函数
int main() {
    SqList s;
    s = {10000, 0, 1, 5, 9, 8, 7, 6, 3, 12, 2,};   //第一位为哨兵,设成一个没用的随便一个值即可
    s.length = 10;
    MergeSort(&s);                                 //调用函数,这里调用上面的那几个排序函数即可。
    for (int i = 1; i <= s.length; i++) {
        printf("%d ", s.r[i]);
    }
}