排序算法篇

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

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

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

基础排序

冒泡排序

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

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

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

比如下面的数组：

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

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

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

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

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

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

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

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

程序代码如下：

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. 如果整轮排序中都没有出现任何的交换，那么说明数组已经是有序的了，不存在前一个比后一个大的情况。

所以，我们来改进一下：

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，数组已经有序，所以说直接结束战斗
    }
}

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

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

插入排序

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

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

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

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

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

比如下面的数组：

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

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

接着插入即可：

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

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

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

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

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

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

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最后在哪个位置，就是是哪个位置插入
    }
}

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

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轮交换之后，得到有序数组。

比如下面的数组：

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

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

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

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

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

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;
    }
}

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

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^2)，那么能否找到更快的排序算法呢？这一部分，我们将继续介绍前面三种排序算法的进阶版本。