排序

这标题看着多友善~
话说在前，其实从博主的学习顺序上来看，这第七章应该是 图 这一部分的内容，但一来认为刚刚说完树，应该让读者（也是让博主）缓一缓节奏，二来排序这一章在C语言的章节中就想着要进一步扩展一下，正好在此直接说完了事。
好嘞，咱正式开始。

在我们C语言的章节中，曾经提过 冒泡排序 这一种最基础，最简单的排序方式。诚然，这种排序方式清晰且易懂，但还是那个问题，耗时太长了，时间复杂度太高。因此本章会介绍更多种排序方式，权当为读者扩展思路。

几个概念

排序

虽然读者应该大体了解了，但这里为了仪式感还是提一嘴。

排序 指的是将一个 无序 的记录序列调整为 有序 的记录序列的过程。

排序的稳定性

排序的稳定性 指的是排序算法对于 相同关键字 进行排序前后的 相对次序 是否有改变。

这个词算是个新词，咱举个例子说一下，比如有如下这么个数组：

2, 1, 5₍₁₎, 8, 7, 5₍₂₎

可以看出，这个序列中有两个 5 ，而在排序之前，这俩元素是有先后顺序的。
如果通过一种排序算法，本来在前面的5₍₁₎还会稳定的处于5₍₂₎的前侧，我们则称这种排序算法是 稳定的 ，反之，如果排完序不确定哪个5在前，我们则称这种排序算法是不稳定的。

内排和外排

内排 是 内部排序 的简称，其意义为将数据存储在计算机的内存中直接进行排序过程。

相对应的， 外排 是 外部排序 的简称，其意义为当需要排序的纪录很多时，内存无法全部一次性容纳，则我们在排序的过程中还需要多次访问外存来完成排序的全过程。

在本章中，我们探讨的主要内容为内部排序。

内部排序的方法

本章中主要涉及到的排序方法有：

• 插入排序
• 交换排序
• 选择排序
• 归并排序
• 基数排序

它们进行排序的方法有区别，进而导致了其时间复杂度的区别，但总归，内部排序的目标，都在于 逐步扩大有序序列长度 。

与以往不同的是，我们这里先对待排序的数据类型进行定义，这是因为不同排序的方法操作的对象总是需要统一的，

#define MAXSIZE 1000 //顺序表长度
typedef int KeyType; //你需要定义的关键词类型（也可以直接写，这里不必要太纠结）

//待排序的数据类型定义
typedef struct{
    KeyType key; //关键字
    InfoType otherinfo //其他数据
}RcdType;

typedef struct{
    RcdType r[MAXSIZE+1]; //在排序中，往往第一个存储区域（即r[0]）处于闲置状态
    int length; //顺序表长度
}SqList; //顺序表类型

好了，接下来我们正式进入算法部分。

插入排序

插入排序的基本思想

插入排序 ，简称插排，基本思想在于将待排序区域划分为已排序区域(R₁, R₂, …, R_i-1)以及未排序部分(R_i, R_i+1, …, R_n)，我们在涉及到 R_i 这个元素时，会先找到其在这个有序序列中应当插入的位置，将其插入，同时其原位置上的元素至原先的已排序区域结尾元素顺序后移一位。

根据上述思路，我们可以将 一趟插入排序 分为以下三步：

• 在有序区域找到插入位置
• 后移后续的有序区元素
• 将设计元素插入到该位置上

与此同时，基于实现方法的不同，插排还有进一步的细分：

• 直接插入
• 折半插入
• 希尔排序
• 表插入

直接插入排序

直接插入排序是最简单的，它直接从后往前找，并每次都进行一次比较，直到找到应当插入的位置为止：

//直接插入排序
void InsertionSort(SqList &L){
    for(int i = 2; i<=L.length; i++){
        //第一个元素不用进行插排，因为它肯定在第一轮时在第一个位置
        if(L.r[i].key<L.r[i-1].key){
            L.r[0] = L.r[i]; //还记得之前定义待排序列空出的下标为0的位置吗，这个位置叫做监视哨。
            //每次排序时会先将待插入的元素赋给监视哨
            for(int j = i-1; L.r[0].key < L.r[j].key; j--){
                L.r[j+1] = L.r[j]; //当没到达插入位置时，将该位置的元素往后移一位
            }
            //for跑完了，就到达插入位置了
            L.r[j+1] = L.r[0]; //再把监视哨的内容插入到这个位置即可
        }
    }
}

上述代码应该注释的很清楚了，读者只需要注意一下这个叫做 监视哨 的玩意，这东西在后续的排序算法中会有很广泛的应用。

这种排序的时间复杂度其实还是挺高，因为其相当于每一次都还得跑两层循环，为O(n²)，正因如此，它也还是只适用于排序的元素非常少的情况。

折半插入排序

我们一寻思了，本来前面的序列就是有序的，那我们干脆用折半查找的方式来找插入位置多好，确实，这就是折半插入排序的基本思路。

//折半插入排序
void BiInsertionSort(SqList &L){
    for(int i = 2; i<=L.length; i++){
        L.r[0] = L.r[i];
        //下面需要通过折半查找找到插入位置
        int low = 1, high = i-1;
        while(low<=high){
            m = (low+high)/2; //折半
            if(L.r[0].key<L.r[m].key){
                high = m-1; //插入点在前半部分
            }else{
                low = m+1; //插入点在后半部分
            }
        } //当找到插入点时，会将low变到high+1（或将high变到low-1），此时不满足循环条件，退出循环
        for(int j = i-1; j>=high+1; j--){
            L.r[j+1] = L.r[j]; //记录后移
        }
        L.r[j+1] = L.r[0]; //插入
    }
}

可以看出，这种排序算法其实时间复杂度总体还是O(n²)，但好在当数据很多时，其寻找插入位置比此前直接插入的方式要快很多，因此还是很值得考虑的。

希尔排序

希尔排序的思路跟此前两者的思路并不相同，它意图先对待排序序列做出 宏观 的调整，此后再将调整范围逐步缩小至 微观 层面。

这个思路确实非常令人眼前一亮，其具体实现方式为先进行 跳跃式的插入排序 ，比如我们将整个序列分为 d个子序列：

R[1], R[1+d], R[1+2d], …, R[1+kd];
R[2], R[2+d], R[2+2d], …, R[2+kd];
…
R[d-1], R[2d-1], R[3d-1], …, R[(k+1)d-1];
R[d], R[2d], R[3d], …, R[(k+1)d];

这个 d 被称为排序过程的增量，而这个量是在逐渐减小的，直到最后一趟排序时它会变成1。

我们在每次排序时，先对每一组中的元素进行排序，最后将d降为1时，就相当于对整体再进行一次直接插入排序。

到这读者可能会问了，这有啥用呢？最后反正都得进行一次插排？

别忘了希尔排序的思想，这个方式使得我们在进行最后的整体插排时，整个序列已经 基本有序 了，这使得最后的直接插排耗时大幅度降低，这就是希尔排序在前面对宏观顺序的调整的价值。

理解了方式，我们给代码：

//希尔排序
void ShellInsert(SqList &L, int d){
    //每一趟希尔排序的函数，该趟增量为d
    for(int i = 1; i<=d; i++){ //对于增量为d的每一组
        for(int j = i+d; j<L.length; j+=d){ //遍历这一组中的每个元素
            L.r[0] = L.r[j]; //将当前元素放在哨兵位
            int t;
            for(t = j-d; t>=0 && L.r[t].key>=L.r[0].key; t-=d){
                //对每一个元素，找到其插入位置
                L.r[t+d] = L.r[t]; //每个插入位置之后的每个元素后移一位
            }
            L.r[t+d] = L.r[0]; //将该元素插入到这一组的适当位置上
        }
    }
}

void ShellSort(SqList &L, int dlta[], int t){
    //dlta数组用于存放每一趟希尔排序的增量，而t用于存储dlta数组的大小
    for(int k = 0; k<t; k++){
        ShellInsert(L, dlta[k]); //对每一趟希尔排序单写函数
    }
}

可以看出，希尔排序的时间复杂度是一个关于dlta序列（即增量序列）的函数。

交换排序

冒泡排序

这种排序咱们很熟悉了，在C语言的篇章中就提及过，但是问题在于效率太低了。

其具体思想在于每一轮排序会逐次进行前后元素的比较并交换，达到每一次将最大元素 / 最小元素放到数组最后的效果，这样进行n-1轮，就能够将数组排序完成。

提一嘴，冒泡排序是可以进行改进的，即单独设置一个变量在每次进行排序时检测是否有交换次数的产生，如果没有交换则可以直接退出该次排序进程（数列已有序）

//冒泡排序
void BubbleSort(SqList &L){
    int i = L.length, flag = 1;
    //flag用于标记是否有交换现象产生
    while(i>1 && flag){
        flag = 0; //在每一轮冒泡之前将标记位置0
        for(int j = 0;j<i;j++){
            if(L.r[j].key>L.r[j+1].key){
                Swap(L.r[j], L.r[j+1]);
                flag = 1;
            }
        }
        i--;
    } //如果有交换现象则继续
}

快速排序（Qsort）

快排的思想也是分轮的，其思想在于分轮排序：

• 一轮快速排序：

目标在于选出一个枢轴，将比它小的元素放到它的左边，再将比它大的元素放到它的右边：

//单轮快速排序
int Partition(SqList &L, int low, int high){
    int pivotkey = L.r[low].key;
    //这个元素作为枢轴
    L.r[0] = pivotkey; //放入哨兵位置
    while(low<high){
        while(low<high && L.r[high].key>=pivotkey){
            high--;
            //如果high指向的元素比枢轴大，则继续搜索
        } //当此时high指向的元素比枢轴小了，将high的元素与low的元素交换
        L.r[low] = L.r[high];
        while(low<high && L.r[low].key<=pivotkey){
            low++;
        }
        L.r[high] = L.r[low];
    } //最终low会与high相同，停止循环，此时low / high的位置就是枢轴应该放到的位置
    L.r[low] = L.r[0];
    return low; //把最后枢轴所在的位置返回
}

• 快速排序

有了一轮排序，我们可以通过多轮快排进行对一整个数组的快排：

//多轮快排
void QSort(SqList &L, int s, int t){
    //对L.r的s至t的位置进行快速排序
    if(s<t){
        //当前需要排序的长度序列大于1
        pivotloc = Partition(L, s, t); //对s到t进行一次划分
        QSort(R, s, pivotloc-1); //对比pivotloc小的序列进行递归
        QSort(R, pivotloc+1, t); //对比pivotloc大的序列进行递归
    }
}

快排的时间复杂度为nlog(n)。

但还存在一个问题，当快速排序要处理的对象本身就有序时，这就势必导致快排效率的退化（因为每次都拿第一个元素当枢轴），这时，快排会退化为冒泡的时间复杂度。

选择排序

简单选择排序

简单排序的思路很简单，我们将数组分为一部分有序序列以及另一部分无序序列，将无序序列中最小 / 最大的元素挑出来，放到有序序列与无序序列分界处的位置。

//简单选择排序
void SelectSort(SqList &L){
    for(int i = 1; i<L.length; i++){
        int j = L.r[i]; //j存储数组中第i小的元素
        //此时前[1, i]的数组已经排序完成，因此在[i+1, L.length]之间寻找最小值
        for(int k = i+1; k<=L.length; k++){
            if(L.r[k]<j){
                j = L.r[k];
            }
        }
        if(i!=j){
            swap(L.r[i], L.r[j]);
            //交换到位
        }
    }
}

其时间复杂度为O(n²)

树形选择排序

树形选择排序的主要优化点在于将 选择最小值 这一过程的时间复杂度降低了。

其采用类似于锦标赛的思路，在无序序列中先让元素两两一组，互相比较，记录两者之间最小的那个，而后在挑选出来的新一组中继续两两一组，如此循环，直至最后只剩下一个元素时，这时就是最小的那个。

这种算法，每一次选出最小值的复杂度是log₂(n)，而显然我们需要进行n次这样的选择，故整体算法的时间复杂度为nlog₂(n)

注：log₂(n)其实就是一棵完全二叉树的深度。

堆排序

这块咱得重点说一下，因为涉及到了一个全新的玩意，叫 堆

堆的定义为满足如下规定的数组：

• r_i <(>) r_2i
• r_i <(>) r_2i+1

这样的数组可以被称为 小顶堆（大顶堆）

其实形象地了解一下，我们借助一下上一章中讲的二叉树的知识，就是将一个数组写成一个二叉树，而其每个双亲结点都要比其子节点要小（大）

那这玩意又跟排序怎么扯上关系呢？

我们拿小顶堆举例子，显然，小顶堆虽然后面的元素顺序不确定，但是其最顶部的元素则很显然是整个数组中最小的那个。

那么，我们只需要对这个数组的n个元素先进行建堆操作，将其调整成小顶堆，而后将最小的那个元素扔到最后边，在对前面的n-1个元素继续进行建堆操作，如此循环往复，就能将这个数组变成一个从大到小的有序数组了。

到这里，就可以引出我们要解决的两个问题了：

• 怎么建堆？
• 堆顶元素扔到最后去了，那我们怎么对剩余元素建立新堆？

咱先说第二个：

我们假设有一个大顶堆：

98, 81, 49, 73, 36, 27, 40, 55, 64, 12

现在把最大的那个元素扔到最后面（即98与12交换）
数组变为：

12, 81, 49, 73, 36, 27, 40, 55, 64, 98

现在要对前n-1个元素继续建堆，其实是一个自上而下 筛选 的过程：
我们先比较12与其两个子节点81，49；
因为要建大顶堆，因此肯定要把最大的元素放到最上边，这三个元素显然81最大，因此将81放到12的位置，交换：

81, 12, 49, 73, 36, 27, 40, 55, 64, 98

好的，继续筛选，12现在下标为2，对应的子结点为4、5，即比较12，73，36；
显然，73要和12换位置：

81, 73, 49, 12, 36, 27, 40, 55, 64, 98

继续筛选，12的下标为4，对应的子节点为8、9，即比较12，55，64；
继续，64和12换位置：

81, 73, 49, 64, 36, 27, 40, 55, 12, 98

好了，目前我们发现12没数可比了，就结束调整，我们发现此时前n-1个元素又变成了一个大顶堆。

注：别忘了在排序中，数组下标从1开始哦（0号元素是哨兵位）。

通过这种方式，我们可以达成调整大顶堆的目的。

那再回到第一个问题，我们就可以用与第二个问题类似的思路继续往下走：

我们想到了，其实建堆的过程就是一个逐层递进，一层一层建立堆的过程：

上面的过程中根结点的两棵子树其实没有变，这就意味着我们如果能把根结点的两棵子树分别调整成大顶堆，就可以再进行一次上面的算法，将整棵树都变成大顶堆。

这就形成了一个循环的思路。

给出代码：

void HeapAdjust(SqList &L, int s, int m){
    //调整大顶堆
    L.r[0] = L.r[s] //哨兵位暂存堆顶元素
    for(int i = 2*s; i<=m; i*=2){
        if(i<m && L.r[i].key < L.r[i+1].key){
            i++;
        } //将i指向子节点中最大的那个元素
        if(L.r[0].key >= L.r[i].key){
            break; //如果堆顶元素比两个元素都大
            // 说明这个当前位置就是堆顶元素应该插入的位置，退出循环
        }else{
            L.r[s] = L.r[i]; s = i;
        } //否则将比较大的那个元素移到顶部，继续下一轮判断
        //这里之所以不是交换是因为L.r[0]已经暂存了我们要调整的元素
    } //结束循环后，s会指向堆顶元素需要插入的位置
    L.r[s] = L.r[0];
}

void HeapSort(SqList &L){
    //堆排序
    for(int i = L.length/2; i>0; i++){
        //从底层树开始一层层调整为大顶堆
        HeapAdjust(L, i, L.length);
    }//将整个数组建成大顶堆
    for(int i = L.length; i>1; i--){
        L.r[0] = L.r[1];
        L.r[1] = L.r[i];
        L.r[i] = L.r[0];
        //将最前面的元素（最大的元素）与未经排序的最后一个元素交换
        HeapAdjust(L, 1, i); //调整成大顶堆
    }
}

堆排序的时间复杂度为O(nlogn);

归并排序

归并排序的思路又不一样了，其思路在于逐次排序，并两两合并。

比如一个数组有8个元素，归并排序是 12 / 34 / 56 / 78 ，将元素分为四组，先将这四组都改为有序列，而后两两合并，即变为 1234 / 5678，再对这两组元素分别排成有序序列，而后继续合并为 12345678，并排序。最终变为有序序列。

每一趟归并的时间复杂度是O(n)，而归并排序总共需要进行O(log₂n)趟

因此归并排序的总时间复杂度为O(nlogn)

基数排序

基数排序针对多关键字，同时根据关键字数位不同，需要进行多次 分配-收集 的过程。

咱举个例子

假如说，有如下这些关键字：
209, 386, 768, 185, 247, 606, 230, 834, 539

我们如果想要将其进行有序排列，除了可以直接进行数字之间的比较外，我们还可以将其看为一个个的个体，即由个位数，十位数，百位数三个部分组成的一个整体。

那我们只需要对三个部分按照合适的顺序分别进行排序即可成功将这个序列变为有序序列。

我们先按个位数来一遍：
230, 834, 185, 386, 606, 247, 768, 209, 539

在个位数的基础上，再按十位数进行排序：
606, 209, 230, 834, 539, 247, 768, 185, 386

而后，在以上两次排序排出序列的基础上，我们再按百位数进行排序：
185, 209, 230, 247, 386, 539, 606, 768, 834

会发现数组已经有序。

以上，是基数排序的一个经典的案例，这个例子很恰当的说明了这种排序方法在多关键字的情况下的适用性。

时间复杂度是O(d(n+rd));

d是 分配-收集 的趟数，rd是 基数的取值范围

总结

OK，这么多种排序过去，咱做个总结。

时间性能：

• O(nlogn) : 快速排序（QSort），堆排序（HeapSort），归并排序（MergeSort）
• O(n²) : 直接插入排序，冒泡排序，简单选择排序
• O(n) : 基数排序（有限制）

如果本来待排序列就有序，则直接插入排序，冒泡排序的时间复杂度进化为 O(n)，而快速排序退化为 O(n²)

空间性能：

空间性能指排序过程中需要的辅助空间大小：

• O(1) : 所有简单排序（插入，冒泡，选择），堆排序
• O(logn) : 快速排序（递归过程占用的栈空间）
• O(n) : 归并排序（需要复制一个数组进行归并的操作）

稳定性：

在文章开头介绍了稳定性的概念。

像快速排序，直接选择排序，堆排序，希尔排序这种有 频繁元素交换操作 的排序方法往往是不稳定的。

本篇博文就到这里~