cover

排序算法篇

恭喜各位小伙伴来到最后一部分：排序算法篇，数据结构与算法的学习也接近尾声了，坚持就是胜利啊！

一个数组中的数据原本是凌乱的，但是由于需要，我们需要使其有序排列，要实现对数组进行排序我们之前已经在C语言程序设计篇中讲解过冒泡排序和快速排序（选学），而这一部分，我们将继续讲解更多种类型的排序算法。

在开始之前，我们还是从冒泡排序开始回顾。

基础排序

冒泡排序

冒泡排序在C语言程序设计篇已经讲解过了，冒泡排序的核心就是交换，通过不断地进行交换，一点一点将大的元素推向一端，每一轮都会有一个最大的元素排到对应的位置上，最后形成有序。算法演示网站：https://visualgo.net/zh/sorting?slide=2-2

设数组长度为N，详细过程为：

  • 共进行N轮排序。
  • 每一轮排序从数组的最左边开始，两两元素进行比较，如果左边元素大于右边的元素，那么就交换两个元素的位置，否则不变。
  • 每轮排序都会将剩余元素中最大的一个推到最右边，下次排序就不再考虑这些已经在对应位置的元素。

比如下面的数组：

image-20220904212453328

那么在第一轮排序时，首先比较前两个元素：

image-20220904212608834

我们发现前者更大，那么此时就需要交换，交换之后，继续向后比较后面的两个元素：

image-20220904212637156

我们发现后者更大，不变，继续看后两个：

image-20220904212720898

此时前者更大，交换，继续比较后续元素：

image-20220904212855292

还是后者更大，继续交换，然后向后比较：

image-20220904212942212

依然是后者更大，我们发现，只要是最大的元素，它会在每次比较中被一直往后丢：

image-20220904213034375

最后，当前数组中最大的元素就被丢到最前面去了，这一轮排序结束，因为最大的已经排到对应的位置上了，所以说第二轮我们只需要考虑其之前的这些元素即可：

image-20220904213115671

这样，我们就可以不断将最大的丢到最右边了，最后N轮排序之后，就是一个有序的数组了。

程序代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(int arr[], int size){
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            //注意需要到N-1的位置就停止，因为要比较j和j+1
            //这里减去的i也就是已经排好的不需要考虑了
            if(arr[j] > arr[j + 1]) {   //如果后面比前面的小，那么就交换
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

只不过这种代码还是最原始的冒泡排序，我们可以对其进行优化：

  1. 实际上排序并不需要N轮，而是N-1轮即可，因为最后一轮只有一个元素未排序了，相当于已经排序了，所以说不需要再考虑了。
  2. 如果整轮排序中都没有出现任何的交换，那么说明数组已经是有序的了，不存在前一个比后一个大的情况。

所以，我们来改进一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int arr[], int size){
    for (int i = 0; i < size - 1; ++i) {   //只需要size-1次即可
        _Bool flag = 1;   //这里使用一个标记，默认为1表示数组是有序的
        for (int j = 0; j < size - i - 1; ++j) {
            if(arr[j] > arr[j + 1]) {
                flag = 0;    //如果发生交换，说明不是有序的，把标记变成0
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
        if(flag) break;   //如果没有发生任何交换，flag一定是1，数组已经有序，所以说直接结束战斗
    }
}

这样，我们才算编写完了一个优化版的冒泡排序。

当然，最后我们还需要介绍一个额外的概念：排序的稳定性，那么什么是稳定性呢？如果说大小相同的两个元素在排序之前和排序之后的先后顺序不变，这个排序算法就是稳定的。我们刚刚介绍的冒泡排序只会在前者大于后者的情况下才会进行交换，所以说不会影响到原本相等的两个元素顺序，因此冒泡排序是稳定的排序算法。

插入排序

我们来介绍一种新的排序算法，插入排序，准确地说应该叫直接插入排序，它的核心思想就像我们玩斗地主一样。

image-20220904214541199

相信各位应该都玩过，每一轮游戏在开始之前，我们都要从牌堆去摸牌，那么摸到牌之后，在我们手中的牌顺序可能是乱的，这样肯定不行啊，牌都没理顺我们怎么知道哪些牌有多少呢？为了使得其有序，我们就会根据牌的顺序，将新摸过来的牌插入到对应的位置上，这样我们后面就不用再整理手里的牌了。

而插入排序实际上也是一样的原理，我们默认前面的牌都是已经排好序的（一开始就只有第一张牌是有序状态），剩余的部分我们会挨着遍历，然后将其插到前面对应的位置上去，动画演示地址：https://visualgo.net/zh/sorting

设数组长度为N，详细过程为：

  • 共进行N轮排序。
  • 每轮排序会从后面依次选择一个元素，与前面已经处于有序的元素，从后往前进行比较，直到遇到一个不大于当前元素的的元素，将当前元素插入到此元素的前面。
  • 插入元素后，后续元素则全部后移一位。
  • 当后面的所有元素全部遍历完成，全部插入到对应的位置之后，排序完成。

比如下面的数组：

image-20220904212453328

此时我们默认第一个元素已经是处于有序状态，我们从第二个元素开始看：

image-20220904221510897

将其取出，从后往前，与前面的有序序列依次进行比较，首先比较的是4，发现比4小，继续向前，发现已经到头了，所以说直接放到最前面即可，注意在放到最前面之前，先将后续元素后移，腾出空间：

image-20220904221648492

接着插入即可：

image-20220904221904359

目前前面两个元素都是有序的状态了，我们继续来看第三个元素：

image-20220904221938583

依然是从后往前看，我们发现上来就遇到了7小的4，所以说直接放到这个位置：

image-20220904222022949

现在前面三个元素都是有序状态了，同样的，我们继续来看第四个元素：

image-20220904222105375

依次向前比较，发现到头了都没找到比1还小的元素，所以说将前面三个元素全部后移：

image-20220904222145903

将1插入到对应的位置上去：

image-20220904222207544

现在前四个元素都是有序的状态了，我们只需要按照同样的方式完成后续元素的遍历，最后得到的就是有序的数组了，我们来尝试编写一下代码：

1
2
3
4
5
6
7
8
9
10
void insertSort(int arr[], int size){
    for (int i = 1; i < size; ++i) {   //从第二个元素开始看
        int j = i, tmp = arr[i];   //j直接变成i，因为前面的都是有序的了，tmp相当于是抽出来的牌暂存一下
        while (j > 0 && arr[j - 1] > tmp) {   //只要j>0并且前一个还大于当前待插入元素，就一直往前找
            arr[j] = arr[j - 1];   //找的过程中需要不断进行后移操作，把位置腾出来
            j--;
        }
        arr[j] = tmp;  //j最后在哪个位置，就是是哪个位置插入
    }
}

当然，这个代码也是可以改进的，因为我们在寻找插入位置上逐个比较，花费了太多的时间，因为前面一部分元素已经是有序状态了，我们可以考虑使用二分搜索算法来查找对应的插入位置，这样就可以节省查找插入点的时间了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int binarySearch(int arr[], int left, int right, int target){
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if(target == arr[mid]) return mid + 1;   //如果插入元素跟中间元素相等，直接返回后一位
        else if (target < arr[mid])  //如果大于待插入元素，说明插入位置肯定在左边
            right = mid - 1;   //范围划到左边
        else   
            left = mid + 1;   //范围划到右边
    }
    return left;   //不断划分范围，left也就是待插入位置了
}

void insertSort(int arr[], int size){
    for (int i = 1; i < size; ++i) {
        int tmp = arr[i];
        int j = binarySearch(arr, 0, i - 1, tmp);   //由二分搜索来确定插入位置
        for (int k = i; k > j; k--) arr[k] = arr[k - 1];   //依然是将后面的元素后移
        arr[j] = tmp;
    }
}

我们最后还是来讨论一下，插入排序算法的稳定性。那么没有经过优化的插入排序，实际上是不断向前寻找到一个不大于待插入元素的元素，所以说遇到相等的元素时只会插入到其后面，并没有更改相同元素原本的顺序，所以说插入排序也是稳定的排序算法（不过后面使用了二分搜索优化之后就不稳定了，比如有序数组中连续两个相等的元素，现在又来了一个相等的元素，此时中间的正好找到的是排在最前面的相等元素，返回其后一个位置，新插入的元素会将原本排在第二个的相等元素挤到后面去了）

选择排序

我们来看看最后一种选择排序（准确的说应该是直接选择排序），这种排序也比较好理解，我们每次都去后面找一个最小的放到前面即可，算法演示网站：https://visualgo.net/zh/sorting

设数组长度为N，详细过程为：

  • 共进行N轮排序。
  • 每轮排序会从后面的所有元素中寻找一个最小的元素出来，然后与已经排序好的下一个位置进行交换。
  • 进行N轮交换之后，得到有序数组。

比如下面的数组：

image-20220904212453328

第一次排序需要从整个数组中寻找一个最小的元素，并将其与第一个元素进行交换：

image-20220905141347927

交换之后，第一个元素已经是有序状态了，我们继续从剩下的元素中寻找一个最小的：

image-20220905141426011

此时2正好在第二个位置，假装交换一下，这样前面两个元素都已经是有序的状态了，我们接着来看剩余的：

image-20220905141527050

此时发现3是最小的，所以说直接将其交换到第三个元素位置上：

image-20220905141629207

这样，前三个元素都是有序的了，通过不断这样交换，最后我们得到的数组就是一个有序的了，我们来尝试编写一下代码：

1
2
3
4
5
6
7
8
9
10
11
void selectSort(int arr[], int size){
    for (int i = 0; i < size - 1; ++i) {   //因为最后一个元素一定是在对应位置上的，所以只需要进行N - 1轮排序
        int min = i;   //记录一下当前最小的元素，默认是剩余元素中的第一个元素
        for (int j = i + 1; j < size; ++j)   //挨个遍历剩余的元素，如果遇到比当前记录的最小元素还小的元素，就更新
            if(arr[min] > arr[j])
                min = j;
        int tmp = arr[i];    //找出最小的元素之后，开始交换
        arr[i] = arr[min];
        arr[min] = tmp;
    }
}

当然，对于选择排序，我们也可以进行优化，因为每次都需要选一个最小的出来，我们不妨再顺手选个最大的出来，小的往左边丢，大的往右边丢，这样就能够有双倍的效率完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void swap(int * a, int * b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void selectSort(int arr[], int size){
    int left = 0, right = size - 1;   //相当于左端和右端都是已经排好序的，中间是待排序的，所以说范围不断缩小
    while (left < right) {
        int min = left, max = right;
        for (int i = left; i <= right; i++) {
            if (arr[i] < arr[min]) min = i;   //同时找最小的和最大的
            if (arr[i] > arr[max]) max = i;
        }
        swap(&arr[max], &arr[right]);   //这里先把大的换到右边
        //注意大的换到右边之后，有可能被换出来的这个就是最小的，所以说需要判断一下
        //如果遍历完发现最小的就是当前右边排序的第一个元素
        //此时因为已经被换出来了，所以说需要将min改到换出来的那个位置
        if (min == right) min = max;
        swap(&arr[min], &arr[left]);   //接着把小的换到左边
        left++;    //这一轮完事之后，缩小范围
        right--;
    }
}

最后我们来分析一下选择排序的稳定性，首先选择排序是每次选择最小的那一个，在向前插入时，会直接进行交换操作，比如原序列为 3,3,1，此时选择出1是最小的元素，与最前面的3进行交换，交换之后，原本排在第一个的3跑到最后去了，破坏了原有的顺序，所以说选择排序是不稳定的排序算法。

我们来总结一下上面所学的三种排序算法，假设需要排序的数组长度为n：

  • 冒泡排序（优化版）：
    • 最好情况时间复杂度：$O(n)$，如果本身就是有序的，那么我们只需要一次遍历，当标记检测到没有发生交换，直接就结束了，所以说一遍就搞定。
    • 最坏情况时间复杂度：$O(n^2)$，也就是硬生生把每一轮都吃满了，比如完全倒序的数组就会这样。
    • **空间复杂度：**因为只需要一个变量来暂存一下需要交换的变量，所以说空间复杂度为 $O(1)$
    • **稳定性：**稳定
  • 插入排序：
    • 最好情况时间复杂度：$O(n)$，如果本身就是有序的，因为插入的位置也是同样的位置，当数组本身就是有序的情况下时，每一轮我们不需要变动任何其他元素。
    • 最坏情况时间复杂度：$O(n^2)$，比如完全倒序的数组就会这样，每一轮都得完完整整找到最前面插入。
    • 空间复杂度：同样只需一个变量来存一下抽出来的元素，所以说空间复杂度为 $O(1)$
    • **稳定性：**稳定
  • 选择排序：
    • 最好情况时间复杂度：$O(n^2)$，即使数组本身就是有序的，每一轮还是得将剩余部分挨个找完之后才能确定最小的元素，所以说依然需要平方阶。
    • 最坏情况时间复杂度：$O(n^2)$，不用多说了吧。
    • 空间复杂度：每一轮只需要记录最小的元素位置即可，所以说空间复杂度为 $O(1)$
    • **稳定性：**不稳定

表格如下，建议记住：

排序算法 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 $O(n)$ $O(n^2)$ $O(1)$ 稳定
插入排序 $O(n)$ $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定

进阶排序

前面我们介绍了三种基础排序算法，它们的平均情况时间复杂度都到达了 $O(n^2)$，那么能否找到更快的排序算法呢？这一部分，我们将继续介绍前面三种排序算法的进阶版本。

快速排序

在C语言程序设计篇，我们也介绍过快速排序，快速排序是冒泡排序的进阶版本，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，就像它的名字一样，速度更快。

实际上快速排序每一轮的目的就是将大的丢到基准右边去，小的丢到基准左边去。

设数组长度为N，详细过程为：

  • 在一开始，排序范围是整个数组
  • 排序之前，我们选择整个排序范围内的第一个元素作为基准，对排序范围内的元素进行快速排序
  • 先从最右边向左看，依次将每一个元素与基准元素进行比较，如果发现比基准元素小，那么就与左边遍历位置上的元素（一开始是基准元素的位置）进行交换，此时保留右边当前遍历的位置。
  • 交换后，转为从左往右开始遍历元素，如果发现比基准元素大，那么就与之前保留的右边遍历的位置上的元素进行交换，同样保留左边当前的位置，循环执行上一个步骤。
  • 当左右遍历撞到一起时，本轮快速排序完成，最后在最中间的位置就是基准元素的位置了。
  • 以基准位置为中心，划分左右两边，以同样的方式执行快速排序。

比如下面的数组：

image-20220904212453328

首先我们选择第一个元素4作为基准元素，一开始左右指针位于两端：

image-20220905210056432

此时从右往左开始看，直到遇到一个比4小的元素，首先是6，肯定不是，将指针往后移动：

image-20220905210625181

此时继续让3和4进行比较，发现比4小，那么此时直接将3交换（其实直接覆盖过去就行了）到左边指针所指向的元素位置：

image-20220905210730105

此时我们转为从左往右看，如果遇到比4大的元素，就交换到右边指针处，3肯定不是了，因为刚刚才缓过来，接着就是2：

image-20220905210851474

2也没有4大，所以说继续往后看，此时7比4要大，那么继续交换：

image-20220905211300102

接着，又开始从右往左看：

image-20220905211344027

此时5是比4要大的，继续向前，发现1比4要小，所以说继续交换：

image-20220905211427939

接着又转为从左往右看，此时两个指针撞到一起了，排序结束，最后两个指针所指向的位置就是给基准元素的位置了：

image-20220905211543845

本轮快速排序结束后，左边不一定都是有序的，但是一定比基准元素要小，右边一定比基准元素大。接着我们以基准为中心，分成两个部分再次进行快速排序：

image-20220905211741787

这样，我们最后就可以使得整个数组有序了，当然快速排序还有其他的说法，有些是左右都找到了再交换，我们这里的是只要找到就丢过去。既然现在思路已经清楚了，我们就来尝试实现一下快速排序吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(int arr[], int start, int end){
    if(start >= end) return;    //范围不可能无限制的划分下去，要是范围划得都没了，肯定要结束了
    int left = start, right = end, pivot = arr[left];   //这里我们定义两个指向左右两个端点的指针，以及取出基准
    while (left < right) {     //只要两个指针没相遇，就一直循环进行下面的操作
        while (left < right && arr[right] >= pivot) right--;   //从右向左看，直到遇到比基准小的
        arr[left] = arr[right];    //遇到比基准小的，就丢到左边去
        while (left < right && arr[left] <= pivot) left++;   //从左往右看，直到遇到比基准大的
        arr[right] = arr[left];    //遇到比基准大的，就丢到右边去
    }
    arr[left] = pivot;    //最后相遇的位置就是基准存放的位置了
    quickSort(arr, start, left - 1);   //不包含基准，划分左右两边，再次进行快速排序
    quickSort(arr, left + 1, end);
}

这样，我们就实现了快速排序。我们还是来分析一下快速排序的稳定性，快速排序是只要遇到比基准小或者大的元素就直接交换，比如原数组就是：2,2,1，此时第一个元素作为基准，首先右边1会被丢过来，变成：1,2,1，然后从左往右，因为只有遇到比基准2更大的元素才会换，所以说最后基准会被放到最后一个位置：1,2,2，此时原本应该在前面的2就跑到后面去了，所以说快速排序算法，是一种不稳定的排序算法。

双轴快速排序（选学）

这里需要额外补充个快速排序的升级版，双轴快速排序，Java语言中的数组工具类则是采用的此排序方式对大数组进行排序的。我们来看看它相比快速排序，又做了哪些改进。首先普通的快速排序算法在遇到极端情况时可能会这样：

image-20220906131959909

整个数组正好是倒序的，那么相当于上来就要把整个数组找完，然后把8放到最后一个位置，此时第一轮结束：

image-20220906132112592

由于8直接跑到最右边了，那么此时没有右半部分，只有做半部分，此时左半部分继续进行快速排序：

image-20220906132244369

此时1又是最小的一个元素，导致最后遍历完了，1都还是在那个位置，此时没有左半部分，只有右半部分：

image-20220906132344525

此时基准是7，又是最大的，真是太倒霉了，排完之后7跑到最左边，还是没有右半部分：

image-20220906132437765

我们发现，在这种极端情况下，每一轮需要完整遍历整个范围，并且每一轮都会有一个最大或是最小的元素被推向两边，这不就是冒泡排序吗？所以说，在极端情况下，快速排序会退化为冒泡排序，因此有些快速排序会随机选取基准元素。为了解决这种在极端情况下出现的问题，我们可以再添加一个基准元素，这样即使出现极端情况，除非两边都是最小元素或是最大元素，否则至少一个基准能正常进行分段，出现极端情况的概率也会减小很多：

image-20220906132945691

此时第一个元素和最后一个元素都作为基准元素，将整个返回划分为三段，假设基准1小于基准2，那么第一段存放的元素全部要小于基准1，第二段存放的元素全部要不小于基准1同时不大于基准2，第三段存放的元素全部要大于基准2：

image-20220906133219853

因此，在划分为三段之后，每轮双轴快排结束后需要对这三段分别继续进行双轴快速排序，最后就可以使得整个数组有序了，当然这种排序算法更适用于哪些量比较大的数组，如果量比较小的话，考虑到双轴快排要执行这么多操作，其实还不如插入排序来的快。

我们来模拟一下双轴快速排序是如何进行的:

image-20220906140255444

首先取出首元素和尾元素作为两个基准，然后我们需要对其进行比较，如果基准1大于基准2，那么需要先交换两个基准，只不过这里因为4小于6，所以说不需要进行交换。

此时我们需要创建三个指针：

image-20220906140538076

因为有三个区域，其中蓝色指针位置及其左边的区域都是小于基准1的，橙色指针左边到蓝色指针之间的区域都是不小于基准1且不大于基准2的，绿色指针位置及其右边的区域都是大于基准2的，橙色指针和绿色指针之间的区域，都是待排序区域。

首先我们从橙色指针所指元素开始进行判断，分三种情况：

  • 如果小于基准1，那么需要先将蓝色指针向后移，把元素交换换到蓝色指针那边去，然后橙色指针也向后移动。
  • 如果不小于基准1且不大于基准2，那么不需要做什么，直接把橙色指针向前移动即可，因为本身就是这个范围。
  • 如果大于基准2，那么需要丢到右边去，先将右边指针左移，不断向前找到一个不比基准2大的，这样才能顺利地交换过去。

首先我们来看看，此时橙色指针指向的是2，那么2是小于基准1的，我们需要先将蓝色指针后移，然后交换橙色和蓝色指针上的元素，只不过这里由于是同一个，所以说不变，此时两个指针都后移了一位：

image-20220906141556398

同样的，我们继续来看橙色指针所指元素，此时为7，大于基准2，那么此时需要在右边找到一个不大于基准2的元素：

image-20220906141653453

绿色指针从右开始向左找，此时找到3，直接交换橙色指针和蓝色指针元素：

image-20220906141758610

下一轮开始继续看橙色指针元素，此时发现是小于基准1的，所以说先向前移动蓝色指针，发现和橙色又在一起了，交换了跟没交换一样，此时两个指针都后移了一位：

image-20220906141926006

新的一轮继续来看橙色指针所指元素，此时我们发现1也是小于基准1的，先移动蓝色指针，再交换，在移动橙色指针，跟上面一样，交换个寂寞：

image-20220906142041202

此时橙色指针指向8，大于基准2，那么同样需要在右边继续找一个不大于基准2的进行交换：

image-20220906142134949

此时找到5，满足条件，交换即可：

image-20220906142205055

我们继续来看橙色指针，发现此时橙色指针元素不小于基准1且不大于基准2，那么根据前面的规则，只需要向前移动橙色指针即可：

image-20220906142303329

此时橙色指针和绿色指针撞一起了，没有剩余待排序元素了，最后我们将两个位于两端点基准元素与对应的指针进行交换，基准1与蓝色指针交换，基准2与绿色指针进行交换：

image-20220906142445417

此时分出来的三个区域，正好满足条件，当然这里运气好，直接整个数组就有序了，不过按照正常的路线，我们还得继续对这剩下的三个区域进行双轴快速排序，最后即可排序完成。

现在我们来尝试编写一下双轴快速排序的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dualPivotQuickSort(int arr[], int start, int end) {
    if(start >= end) return;     //首先结束条件还是跟之前快速排序一样，因为不可能无限制地分下去，分到只剩一个或零个元素时该停止了
    if(arr[start] > arr[end])    //先把首尾两个基准进行比较，看看谁更大
        swap(&arr[start], &arr[end]);    //把大的换到后面去
    int pivot1 = arr[start], pivot2 = arr[end];    //取出两个基准元素
    int left = start, right = end, mid = left + 1;   //因为分了三块区域，此时需要三个指针来存放
    while (mid < right) {    //因为左边冲在最前面的是mid指针，所以说跟之前一样，只要小于right说明mid到right之间还有没排序的元素
        if(arr[mid] < pivot1)     //如果mid所指向的元素小于基准1，说明需要放到最左边
            swap(&arr[++left], &arr[mid++]);   //直接跟最左边交换，然后left和mid都向前移动
        else if (arr[mid] <= pivot2) {    //在如果不小于基准1但是小于基准2，说明在中间
            mid++;   //因为mid本身就是在中间的，所以说只需要向前缩小范围就行
        } else {    //最后就是在右边的情况了
            while (arr[--right] > pivot2 && right > mid);  //此时我们需要找一个右边的位置来存放需要换过来的元素，注意先移动右边指针
            if(mid >= right) break;   //要是把剩余元素找完了都还没找到一个比基准2小的，那么就直接结束，本轮排序已经完成了
            swap(&arr[mid], &arr[right]);   //如果还有剩余元素，说明找到了，直接交换right指针和mid指针所指元素
        }
    }
    swap(&arr[start], &arr[left]);    //最后基准1跟left交换位置，正好左边的全部比基准1小
    swap(&arr[end], &arr[right]);     //最后基准2跟right交换位置，正好右边的全部比基准2大
    dualPivotQuickSort(arr, start, left - 1);    //继续对三个区域再次进行双轴快速排序
    dualPivotQuickSort(arr, left + 1, right - 1);
    dualPivotQuickSort(arr, right + 1, end);
}

此部分仅作为选学，不强制要求。

希尔排序

希尔排序是直接插入排序的进阶版本（希尔排序又叫缩小增量排序）插入排序虽然很好理解，但是在极端情况下会出现让所有已排序元素后移的情况（比如刚好要插入的是一个特别小的元素）为了解决这种问题，希尔排序对插入排序进行改进，它会对整个数组按照步长进行分组，优先比较距离较远的元素。

这个步长是由一个增量序列来定的，这个增量序列很关键，大量研究表明，当增量序列为 dlta[k] = 2^(t-k+1)-1（0<=k<=t<=(log2(n+1))）时，效率很好，只不过为了简单，我们一般使用 $\frac {n} {2}$、$\frac {n} {4}$、$\frac {n} {8}$、…、1 这样的增量序列。

设数组长度为N，详细过程为：

  • 首先求出最初的步长，n/2即可。
  • 我们将整个数组按照步长进行分组，也就是两两一组（如果n为奇数的话，第一组会有三个元素）
  • 我们分别在这些分组内进行插入排序。
  • 排序完成后，我们将步长/2，重新分组，重复上述步骤，直到步长为1时，插入排序最后一遍结束。

这样的话，因为组内就已经调整好了一次顺序，小的元素尽可能排在前面，即使在最后一遍排序中出现遇到小元素要插入的情况，也不会有太多的元素需要后移。

我们以下面的数组为例：

image-20220905223505975

首先数组长度为8，直接整除2，得到34，那么步长就是4了，我们按照4的步长进行分组：

image-20220905223609936

其中，4、8为第一组，2、5 为第二组，7、3为第三组，1、6为第四组，我们分别在这四组内进行插入排序，组内排序之后的结果为：

image-20220905223659584

可以看到目前小的元素尽可能地在往前面走，虽然还不是有序的，接着我们缩小步长，4/2=2，此时按照这个步长划分：

image-20220905223804907

此时4、3、8、7为一组，2、1、5、6为一组，我们继续在这两个组内进行排序，得到：

image-20220905224111803

最后我们继续将步长/2，得到2/2=1，此时步长变为1，也就相当于整个数组为一组，再次进行一次插入排序，此时我们会发现，小的元素都靠到左边来了，此时再进行插入排序会非常轻松。

我们现在就来尝试编写一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void shellSort(int arr[], int size){
    int delta = size / 2;
    while (delta >= 1) {
        //这里依然是使用之前的插入排序，不过此时需要考虑分组了
        for (int i = delta; i < size; ++i) {   //我们需要从delta开始，因为前delta个组的第一个元素默认是有序状态
            int j = i, tmp = arr[i];   //这里依然是把待插入的先抽出来
            while (j >= delta && arr[j - delta] > tmp) {   
              	//注意这里比较需要按步长往回走，所以说是j - delta，此时j必须大于等于delta才可以，如果j - delta小于0说明前面没有元素了
                arr[j] = arr[j - delta];
                j -= delta;
            }
            arr[j] = tmp;
        }
        delta /= 2;    //分组插排完事之后，重新计算步长
    }
}

虽然这里用到了三层循环嵌套，但是实际上的时间复杂度可能比 $O(n^2)$ 还小，因为能够保证小的元素一定往左边靠，所以排序次数实际上并没有我们想象中的那么多，由于证明过程过于复杂，这里就不列出了。

那么希尔排序是不是稳定的呢？因为现在是按步长进行分组，有可能会导致原本相邻的两个相同元素，后者在自己的组内被换到前面去了，所以说希尔排序是不稳定的排序算法。

堆排序

我们来看最后一种，堆排序也是选择排序的一种，但是它能够比直接选择排序更快。还记得我们前面讲解的大顶堆和小顶堆吗？我们来回顾一下：

对于一棵完全二叉树，树中父亲结点都比孩子结点小的我们称为小根堆（小顶堆），树中父亲结点都比孩子结点大则是大根堆

得益于堆是一棵完全二叉树，我们可以很轻松地使用数组来进行表示：

image-20220818110224673

我们通过构建一个堆，就可以将一个无序的数组依次输入，最后存放的序列是一个按顺序排放的序列，利用这种性质，我们可以很轻松地利用堆进行排序，我们先来写一个小顶堆：

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
typedef int E;
typedef struct MinHeap {
    E * arr;
    int size;
    int capacity;
} * Heap;

_Bool initHeap(Heap heap){
    heap->size = 0;
    heap->capacity = 10;
    heap->arr = malloc(sizeof (E) * heap->capacity);
    return heap->arr != NULL;
}

_Bool insert(Heap heap, E element){
    if(heap->size == heap->capacity) return 0;
    int index = ++heap->size;
    while (index > 1 && element < heap->arr[index / 2]) {
        heap->arr[index] = heap->arr[index / 2];
        index /= 2;
    }
    heap->arr[index] = element;
    return 1;
}

E delete(Heap heap){
    E max = heap->arr[1], e = heap->arr[heap->size--];
    int index = 1;
    while (index * 2 <= heap->size) {
        int child = index * 2;
        if(child < heap->size && heap->arr[child] > heap->arr[child + 1])
            child += 1;
        if(e <= heap->arr[child]) break;
        else heap->arr[index] = heap->arr[child];
        index = child;
    }
    heap->arr[index] = e;
    return max;
}

接着我们只需要将这些元素挨个插入到堆中，然后再挨个拿出来，得到的就是一个有序的顺序了：

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
    int arr[] = {3, 5, 7, 2, 9, 0, 6, 1, 8, 4};

    struct MinHeap heap;    //先创建堆
    initHeap(&heap);
    for (int i = 0; i < 10; ++i)
        insert(&heap, arr[i]);   //直接把乱序的数组元素挨个插入
    for (int i = 0; i < 10; ++i)
        arr[i] = delete(&heap);    //然后再一个一个拿出来，就是按顺序的了

    for (int i = 0; i < 10; ++i)
        printf("%d ", arr[i]);
}

最后得到的结果为：

image-20220906001134488

虽然这样用起来比较简单，但是需要额外 $O(n)$ 的空间来作为堆，所以我们可以对其进行进一步的优化，减少其空间上的占用。那么怎么进行优化呢，我们不妨换个思路，直接对给定的数组进行堆的构建。

设数组长度为N，详细过程为：

  • 首先将给定的数组调整为一个大顶堆
  • 进行N轮选择，每次都选择大顶堆顶端的元素从数组末尾开始向前存放（交换堆顶和堆的最后一个元素）
  • 交换完成后，重新对堆的根结点进行调整，使其继续满足大顶堆的性质，然后重复上述操作。
  • 当N轮结束后，得到的就是从小到大排列的数组了。

我们先将给定数组变成一棵完全二叉树，以下面数组为例：

image-20220906220020172

此时，这棵二叉树还并不是堆，我们的首要目标是将其变成一个大顶堆。那么怎么将这棵二叉树变成一个大顶堆呢？我们只需要从最后一个非叶子结点（从上往下的顺序）开始进行调整即可，比如此时1是最后一个非叶子结点，所以说就从1开始，我们需要进行比较，如果其孩子结点大于它，那么需要将最大的那个孩子交换上来，此时其孩子结点6大于1，所以说需要交换：

image-20220906221306519

接着我们来看倒数第二个非叶子结点，也就是7，那么此时两个孩子都是小于它的，所以说不需要做任何调整，我们接着来看倒数第三个非叶子结点2，此时2的两个孩子6、8都大于2，那么我们选择两个孩子里面一个最大的交换上去：

image-20220906221504364

最后就剩下根结点这一个非叶子结点了，此时我们4的左右孩子都大于4，那么依然需要进行调整：

![image-20220906221657599](/Users/nagocoler/Library/Application Support/typora-user-images/image-20220906221657599.png)

在调整之后，还没有结束，因为此时4换下去之后依然不满足大顶堆的性质，此时4的左孩子大于4，我们还需要继续向下看：

image-20220906221833012

交换之后，此时整个二叉树就满足大顶堆的性质了，我们第一次初始调整也就完成了。

此时开始第二步，我们需要一个一个地将堆顶元素往后面进行交换，相当于每次都去取一个最大的出来，直到取完，首先交换堆顶元素和最后一个元素：

image-20220906222327297

此时整个数组中最大的元素已经排到对应的位置上了，然后我们不再考虑最后一个元素，此时将前面的剩余元素继续看做一棵完全二叉树，对根结点重新进行一次堆化（只需要调整根结点即可，因为其他非叶子结点的没有变动），使得其继续满足大顶堆的性质：

image-20220906222819554

还没完，继续调整：

image-20220906222858752

此时第一轮结束，接着第二轮，重复上述操作，首先依然是将堆顶元素丢到倒数第二个位置上，相当于将倒数第二大的元素放到对应的位置上去：

image-20220906222934602

此时已经有两个元素排好序了，同样的，我们继续将剩余元素看做一个完全二叉树，继续对根结点进行堆化操作，使得其继续满足大顶堆性质：

image-20220906223110734

第三轮同样的思路，将最大的交换到后面去：

image-20220906223326135

通过N轮排序，最后每一个元素都可以排到对应的位置上了，根据上面的思路，我们来尝试编写一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//这个函数就是对start顶点位置的子树进行堆化
void makeHeap(int* arr, int start, int end) {
    while (start * 2 + 1 <= end) {    //如果有子树，就一直往下，因为调整之后有可能子树又不满足性质了
        int child = start * 2 + 1;    //因为下标是从0开始，所以左孩子下标就是i * 2 + 1，右孩子下标就是i * 2 + 2
        if(child + 1 <= end && arr[child] < arr[child + 1])   //如果存在右孩子且右孩子比左孩子大
            child++;    //那就直接看右孩子
        if(arr[child] > arr[start])   //如果上面选出来的孩子，比父结点大，那么就需要交换，大的换上去，小的换下来
            swap(&arr[child], &arr[start]);
        start = child;   //继续按照同样的方式前往孩子结点进行调整
    }
}

void heapSort(int arr[], int size) {
    for(int i= size/2 - 1; i >= 0; i--)   //我们首选需要对所有非叶子结点进行一次堆化操作，需要从最后一个到第一个，这里size/2计算的位置刚好是最后一个非叶子结点
        makeHeap(arr, i, size - 1);
    for (int i = size - 1; i > 0; i--) {   //接着我们需要一个一个把堆顶元素搬到后面，有序排列
        swap(&arr[i], &arr[0]);    //搬运实际上就是直接跟倒数第i个元素交换，这样，每次都能从堆顶取一个最大的过来
        makeHeap(arr, 0, i - 1);   //每次搬运完成后，因为堆底元素被换到堆顶了，所以需要再次对根结点重新进行堆化
    }
}

最后我们来分析一下堆排序的稳定性，实际上堆排序本身也是在进行选择，每次都会选择堆顶元素放到后面，只不过堆是一直在动态维护的。实际上从堆顶取出元素时，都会与下面的叶子进行交换，有可能会出现：

image-20220906223706019

所以说堆排序是不稳定的排序算法。

最后我们还是来总结一下上面的三种排序算法的相关性质：

排序算法 最好情况 最坏情况 空间复杂度 稳定性
快速排序 $O(nlogn)$ $O(n^2)$ $O(logn)$ 不稳定
希尔排序 $O(n^{1.3})$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定

其他排序方案

除了我们前面介绍的几种排序算法之外，还有一些其他类型的排序算法，我们都来认识一下吧。

归并排序

归并排序利用递归分治的思想，将原本的数组进行划分，然后首先对划分出来的小数组进行排序，然后最后在合并为一个有序的大数组，还是很好理解的：

image-20220906232451040

我们以下面的数组为例：

image-20220905223505975

在一开始我们先不急着进行排序，我们先一半一半地进行划分：

image-20220907135544173

继续进行划分：

image-20220907135744253

最后会变成这样的一个一个的元素：

image-20220907135927289

此时我们就可以开始归并排序了，注意这里的合并并不是简简单单地合并，我们需要按照从小到大的顺序，依次对每个元素进行合并，第一组树4和2，此时我们需要从这两个数组中先选择小的排到前面去:

image-20220907140219455

排序完成后，我们继续向上合并：

image-20220907141217008

最后我们再将这两个数组合并到原有的规模：

image-20220907141442229

最后就能得到一个有序的数组了。

实际上这种排序算法效率也很高，只不过需要牺牲一个原数组大小的空间来对这些分解后的数据进行排序，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void merge(int arr[], int tmp[], int left, int leftEnd, int right, int rightEnd){
    int i = left, size = rightEnd - left + 1;   //这里需要保存一下当前范围长度，后面使用
    while (left <= leftEnd && right <= rightEnd) {   //如果两边都还有，那么就看哪边小，下一个就存哪一边的
        if(arr[left] <= arr[right])   //如果左边的小，那么就将左边的存到下一个位置（这里i是从left开始的）
            tmp[i++] = arr[left++];   //操作完后记得对i和left都进行自增
        else
            tmp[i++] = arr[right++];
    }
    while (left <= leftEnd)    //如果右边看完了，只剩左边，直接把左边的存进去
        tmp[i++] = arr[left++];
    while (right <= rightEnd)   //同上
        tmp[i++] = arr[right++];
    for (int j = 0; j < size; ++j, rightEnd--)   //全部存到暂存空间中之后，暂存空间中的内容都是有序的了，此时挨个搬回原数组中（注意只能搬运范围内的）
        arr[rightEnd] = tmp[rightEnd];
}

void mergeSort(int arr[], int tmp[], int start, int end){   //要进行归并排序需要提供数组和原数组大小的辅助空间
    if(start >= end) return;   //依然是使用递归，所以说如果范围太小，就不用看了
    int mid = (start + end) / 2;   //先找到中心位置，一会分两半
    mergeSort(arr, tmp, start, mid);   //对左半和右半分别进行归并排序
    mergeSort(arr, tmp, mid + 1, end);
    merge(arr, tmp, start, mid, mid + 1, end);  
  	//上面完事之后，左边和右边都是有序状态了，此时再对整个范围进行一次归并排序即可
}

因为归并排序最后也是按照小的优先进行合并，如果遇到相等的，也是优先将前面的丢回原数组，所以说排在前面的还是排在前面，因此归并排序也是稳定的排序算法。

桶排序和基数排序

在开始讲解桶排序之前，我们先来看看计数排序，它要求是数组长度为N，且数组内的元素取值范围是0 - M-1 之间（M小于等于N）

算法演示网站：https://visualgo.net/zh/sorting?slide=1

比如下面的数组，所有的元素范围是 1-6之间：

image-20220907142933725

我们先对其进行一次遍历，统计每个元素的出现次数，统计完成之后，我们就能够明确在排序之后哪个位置可以存放值为多少的元素了：

image-20220907145336855

我们来分析一下，首先1只有一个，那么只会占用一个位置，2也只有一个，所以说也只会占用一个位置，以此类推：

image-20220907145437992

所以说我们直接根据统计的结果，把这些值挨个填进去就行了，而且还是稳定的，按顺序，有几个填几个就可以了：

image-20220907145649061

是不是感觉很简单，而且只需要遍历一次进行统计就行了。

当然肯定是有缺点的：

  1. 当数组中最大最小值差距过大时，我们得申请更多的空间来进行计数，所以不适用于计数排序。
  2. 当数组中元素值不是离散的（也就是不是整数的情况下）就没办法统计了。

我们接着来看桶排序，它是计数排序的延伸，思路也比较简单，它同样要求是数组长度为N，且数组内的元素取值范围是0 - M-1 之间（M小于等于N），比如现在有1000个学生，现在需要对这些学生按照成绩进行排序，因为成绩的范围是0-100，所以说我们可以建立101个桶来分类存放。

比如下面的数组：

image-20220907142933725

此数组中包含1-6的元素，所以说我们可以建立 6个桶来进行统计：

image-20220907143715938

这样，我们只需要遍历一次，就可以将所有的元素分类丢到这些桶中，最后我们只需要依次遍历这些桶，然后把里面的元素拿出来依次存放回去得到的就是有序的数组了：

image-20220907144255326

只不过桶排序虽然也很快，但是同样具有与上面计数排序一样的限制，我们可以将每个桶接纳一定范围内的元素，来减小桶的数量，但是这样会导致额外的时间开销。

我们最后来看看基数排序，基数排序依然是一种依靠统计来进行的排序算法，但是它不会因为范围太大而导致无限制地申请辅助空间。它的思路是，分出10个基数出来（从0 - 9）我们依然是只需要遍历一次，我们根据每一个元素的个位上的数字，进行分类，因为现在有10个基数，也就是10个桶。个位完事之后再看十位、百位…

算法演示网站：https://visualgo.net/zh/sorting

image-20220907152403435

先按照个位数进行统计，然后排序，再按照十位进行统计，然后排序，最后得到的结果就是最终的结果了：

image-20220907152903020

然后是十位数：

image-20220907153005797

最后再次按顺序取出来：
image-20220907153139536

成功得到有序数组。

最后我们来总结一下所有排序算法的相关性质：

排序算法 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 $O(n)$ $O(n^2)$ $O(1)$ 稳定
插入排序 $O(n)$ $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
快速排序 $O(nlogn)$ $O(n^2)$ $O(logn)$ 不稳定
希尔排序 $O(n^{1.3})$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
计数排序 $O(n + k)$ $O(n + k)$ $O(k)$ 稳定
桶排序 $O(n + k)$ $O(n^2)$ $O(k + n)$ 稳定
基数排序 $O(n \times k)$ $O(n \times k)$ $O(k+n)$ 稳定

猴子排序

猴子排序比较佛系，因为什么时候能排完，全看运气！

无限猴子定理最早是由埃米尔·博雷尔在1909年出版的一本谈概率的书籍中提到的，此书中介绍了“打字的猴子”的概念。无限猴子定理是概率论中的柯尔莫哥洛夫的零一律的其中一个命题的例子。大概意思是，如果让一只猴子在打字机上随机地进行按键，如果一直不停的这样按下去，只要时间达到无穷时，这只猴子就几乎必然可以打出任何给定的文字，甚至是莎士比亚的全套著作也可以打出来。

假如现在有一个长度为N的数组：

image-20220907154254943

我们每次都随机从数组中挑一个元素，与随机的一个元素进行交换：

image-20220907154428792

只要运气足够好，那么说不定几次就可以搞定，要是运气不好，说不定等到你孙子都结婚了都还没排好。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
_Bool checkOrder(int arr[], int size){
    for (int i = 0; i < size - 1; ++i)
        if(arr[i] > arr[i + 1]) return 0;
    return 1;
}

int main(){
    int arr[] = {3,5, 7,2, 9, 0, 6,1, 8, 4}, size = 10;

    int counter = 0;
    while (1) {
        int a = rand() % size, b = rand() % size;
        swap(&arr[a], &arr[b]);
        if(checkOrder(arr, size)) break;
        counter++;
    }
    printf("在第 %d 次排序完成！", counter);
}

可以看到在10个元素的情况下，这边第7485618次排序成功了：

image-20220907160219493

但是不知道为什么每次排序出来的结果都是一样的，可能是随机数取得还不够随机吧。

排序算法 最好情况 最坏情况 空间复杂度 稳定性
猴子排序 $O(1)$ ∞ $O(1)$ 不稳定