排序算法

发表于 2023-07-16 更新于 2023-07-17 分类于算法阅读次数： Waline：阅读次数：本文字数： 5.4k 阅读时长 ≈ 20 分钟

介绍了 7 种排序算法，不包括基数排序等这类骚操作

排序算法概述

对排序严格点得到定义是：假设含有 $n$ 个记录的序列为 $\left\{r_1, r_2, \cdots, r_n\right\}$，其相对应的关键字分别为：$\left\{k_1, k_2, \cdots, k_n\right\}$，需确定 $1,2,3,\cdots,n$ 的一种排列 $p_1,p_2,\cdots,p_n$，使其相应的关键字满足 $k_{p_1} \leqslant k_{p_2} \leqslant \cdots \leqslant k_{p_n}$ 非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列：$\left\{r_{p_1},r_{p_2},\cdots,r_{p_n}\right\}$，这样的操作就成为排序。

排序算法的稳定性：对于一个排序算法，假设 $k_i=k_j \left(1\leqslant i \leqslant n, 1\leqslant j\leqslant n,i \neq j\right)$，且在排序前的序列中 $r_i$ 领先于 $r_j$（即 $i \lt j$）。如果排序后 $r_i$ 仍领先于 $r_j$，则称所用的排序算法是稳定的，否则是不稳定的

排序可分为内排序与外排序，内排序在排序过程中数据全部放置在内存中，外排序由于数据太对，不能将数据一次性加载在内存中，在排序过程中需要多次在内外存直接交换数据。

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 $\Omicron \left(n \log n\right)$，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

对于排序算法的评价也是从时间和空间的角度出发，即排序的时间和所用的额外空间。排序算法的时间开销主要由比较和移动产生。额外空间的产生是因为有些算法需要借助辅助空间才能完成。

本文会介绍冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、桶排序、计数排序和基数排序，其中冒泡排序、选择排序和插入排序是简单的排序算法，希尔排序、归并排序、堆排序、快速快速排序是改进算法。

排序算法性能总结表：

冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数组，一次比较两个元素，如果它们逆序就把它们交换过来。遍历数组的工作是重复地进行直到没有再需要交换的相邻元素，也就是说该数组已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢「浮」到数组的后面。

代码如下：

void bubble_sort(int *arr, int n) {
    for (int i = n - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

实际上如果在某一轮中没有进行交换操作，则说明数组已经有序，所以此时可结束排序，可利用这一点进行代码优化，优化后的代码如下：

void bubble_sort(int *arr, int n) {
    bool flag = false;
    for (int i = n - 1; i > 0; --i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

复杂度分析：对于改进后的算法，最好的情况是数组本来就是有序的，只是进行了 $n - 1$ 次的比较，所以时间复杂度为 $\Omicron \left(n\right)$；最坏的情况就是数组是逆序的时候，此时比较次数为： \[ \sum_{i=2}^{n}\left(i - 1\right) = \frac{n \left(n - 1\right)}{2} \] 比较次数也是相同数量级的，所以时间复杂度为 $\Omicron \left(n^2\right)$.

在相邻元素相等时，不交换它们的位置可保证算法是稳定的算法。

选择排序

选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。

选择排序进行进行 $n - 1$ 次遍历，每次遍历从 $\left[i + 1 ,n\right]$ 这个区间中选出最小值与第 $i$ 个元素交换（当然如果第 $i$ 个元素是最小的则无需交换）。

代码如下：

void selection_sort(int *arr, int n) {
    if (arr == nullptr)
        return;
    if (n <= 1)
        return;
    for (int i = 0; i < n - 1; ++i) {
        int idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[idx]) {
                idx = j;
            }
        }
        if (idx != i) {
            int t = arr[idx];
            arr[idx] = arr[i];
            arr[i] = t;
        }
    }
}

复杂度分析：无论什么情况，比较次数是一样多的，第 $i$ 趟排序的需要比较 $n - i$ 次，比较次数为： \[ \sum_{i=1}^{n-1}\left(n - i\right) = \frac{n \left(n - 1\right)}{2} \] 最好情况下交换次数为 $0$，最坏情况下交换次数为 $n - 1$，所以时间复杂度为 $\Omicron \left(n^2\right)$. 选择排序的略优于冒泡排序。

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

代码如下：

void insertion_sort(int *arr, int n) {
    if (arr == nullptr || n <= 1) {
        return;
    }
    for (int i = 1; i < n; ++i) {
        int tmp = arr[i];
        int j = i;
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            --j;
        }
        if (j != i) {
            arr[j] = tmp;
        }
    }
}

复杂度分析：最好情况下做了 $n - 1$ 次比较，没有移动操作，时间复杂度为 $\Omicron \left(n^2\right)$. 最坏的情况下，即数组是逆序的，比较次数为： \[ \sum_{i=2}^{n}i = \frac{\left(n + 2\right)\left(n - 1\right)}{2} \] 移动次数也达到最大值： \[ \sum_{i=2}^{n}\left(i + 1\right) = \frac{\left(n + 4\right)\left(n - 1\right)}{2} \] 平均比较和移动次数约为 $\frac{n^2}{4}$. 所以，插入排序的复杂度为 $\Omicron \left(n^2\right)$.

插入排序优于冒泡排序和选择排序。

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录「基本有序」时，再对全体记录进行依次直接插入排序。

687474703a2f2f75706c6f61642d696d616765732e6a69616e7368752e696f2f75706c6f61645f696d616765732f31393430

选择一个增量序列 $t_1, t_2，\cdots,t_k$，其中对于 $i \gt j$，有 $t_i \gt t_j$，且 $t_k = 1$。按增量序列个数 $k$，对序列进行 $k$ 趟排序；每趟排序，根据对应的增量 $t_i$，将待排序列分割成若干长度为 $m$ 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码如下：

void shell_sort(int *arr, int n) {
    int h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < n; ++i) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                int tmp = arr[j];
                arr[j] = arr[j - h];
                arr[j - h] = tmp;
            }
        }
        h /= 3;
    }
}

复杂度分析：对增量的选取很重要，这里增量通过 h = 3 * h + 1 的方式得到，但迄今为止没有找到一个非常好的增量选取方式。不过大量研究表明，当增量序列为 $\text{delta[k]} = 2^{t-k+1}-1\left(0 \leqslant k \leqslant \lfloor\log_2{(n+1)}\rfloor\right)$ 时，可以获得不错的效果，时间复杂度为 $\Omicron \left(n^{\frac{3}{2}}\right)$，要好于直接插入排序的 $\Omicron \left(n^2\right)$。需要注意的是，增量排序的最好一个增量值必须等于 1 才行。由于数据是跳跃式的移动，希尔排序不是稳定的排序算法。

希尔排序是第一个突破 $\Omicron \left(n^2\right)$ 的排序算法。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代。

算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

代码如下：

void meger_sort(int arr[], int tmp[], int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) >> 1;
    meger_sort(arr, tmp, l, mid);
    meger_sort(arr, tmp, mid + 1, r);
    int i = l;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r) {
        if (arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= r) {
        tmp[k++] = arr[j++];
    }
    for (int i = l, j = 0; i <= r; ++i, ++j) {
        arr[i] = tmp[j];
    }
}

注意，我这里给出的代码的区间的边界值都是可以取到的

复杂度分析：递归树的每层的时间为 $\Omicron \left(n\right)$，树的高度为 $\lceil\log_2{(n)}\rceil$，所以时间复杂度为 $\Omicron \left(n \log n \right)$. 这是归并排序最好、最坏和平均时间复杂度。由于归并排序需要递归和借助一个数组，所以空间复杂度为 $\Omicron \left(n + \log n\right)$。可以看出，归并排序是一个稳定的排序算法，是一个比较占用空间但效率较高的算法。

当然有非递归的归并排序：

void merge_sort(int arr[], int n) {
    int *a = arr;
    int *b = new int[n];
    for (int i = 1; i < n; i += i) {
        for (int j = 0; j < n; j += i + i) {
            int mid = min(i + j, n) - 1;
            int k = j;

            int l1 = j, r1 = mid;
            int l2 = mid + 1, r2 = min(j + i + i, n) - 1;

            while (l1 <= r1 && l2 <= r2) {
                b[k++] = a[l1] < a[l2] ? a[l1++] : a[l2++];
            }
            while (l1 <= r1) {
                b[k++] = a[l1++];
            }
            while (l2 <= r2) {
                b[k++] = a[l2++];
            }
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < n; ++i) {
            b[i] = a[i];
        }
        b = a;
    }
    delete[] b;
}

非递归的归并排序的空间复杂度为 $\Omicron \left(n \right)$.

快速排序

快速排序是由东尼 · 霍尔所发展的一种排序算法。在平均状况下，排序 $n$ 个项目要 $\Omicron \left(n \log n \right)$ 次比较。在最坏状况下则需要 $\Omicron \left(n^2 \right)$ 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 $\Omicron \left(n \log n \right)$ 算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序的基本思想是：通过一趟排序将待排序记录分隔成独立的两部分，其中一部分记录的关键字均比另外一部分记录关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序使用分治法策略来把一个串行分为两个子串行。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 $\Omicron \left(n^2 \right)$，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 $\Omicron \left(n \log n \right)$ 的排序算法表现要更好，可是这是为什么呢，《算法艺术与信息学竞赛》上说：

快速排序的最坏运行情况是 $\Omicron \left(n^2 \right)$，比如说顺序数列的快排。但它的平摊期望时间是 $\Omicron \left(n \log n \right)$，且 $\Omicron \left(n \log n \right)$ 记号中隐含的常数因子很小，比复杂度稳定等于 $\Omicron \left(n \log n \right)$ 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法步骤：

从数列中挑出一个元素，称为「基准」（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

代码如下：

void quick_sort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    int x = arr[(l + r) / 2];
    int i = l - 1;
    int j = r + 1;
    while (i < j) {
        while (arr[++i] < x)
            ;
        while (arr[--j] > x)
            ;
        if (i < j) {
            swap(arr[i], arr[j]);
        } else {
            break;
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

注意，我这里给出的代码的区间的边界值都是可以取到的。

复杂度分析：在最好的情况下，基准值每次划分的很均匀，如果排序 $n$ 个关键字，其递归树的深度为 $\lfloor\log_2{n} + 1\rfloor$，需递归 $\log_2$ 次，需要的时间为 $T\left(n\right)$ 的话，第一个划分时需要将整个数组扫描一遍，做 $n$ 次比较，基准值将数组一分为二，那么各种还需要 $T\left(\frac{n}{2}\right)$ 的时间。于是乎我们可以得到如下公式： \[ \begin{aligned} T\left(n\right) &\leqslant T\left(\frac{n}{2}\right),T\left(1\right)=0\\ T\left(n\right) &\leqslant 2\left(2T\left(\frac{n}{4}\right) + \frac{n}{2}\right) = 4T\left(\frac{n}{4}\right) + 2n\\ T\left(n\right) &\leqslant 4\left(2T\left(\frac{n}{8}\right) + \frac{n}{4}\right) = 8T\left(\frac{n}{8}\right) + 3n \\ \cdots \\ T\left(n\right) &\leqslant nT\left(1\right) + \left(\log_2 n\right) \times n = \Omicron \left(n \log n \right) \end{aligned} \]

也就是说，在最优的情况下，快速排序算法的时间复杂度是 $\Omicron \left(n \log n \right)$.

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，另外一个为空。把递归树画出来，他就是一颗斜树。此时需要执行 $n - 1$ 次递归调用，且第 $i$ 次划分需要经过 $n - i$ 次关键字的比较才能找到第 $i$ 个记录，因此比较次数为： \[ \sum_{i=1}^{n - 1}\left(n - i\right) = n -1 + n - 2 + \cdots + 1 = \frac{n(n - 1)}{2} \] 其最终时间复杂度为 $\Omicron \left( n^2 \right)$.

平均情况下，时间复杂度也为 $\Omicron \left(n \log n \right)$.

基准值的选取对快速排序的效率较大，我们可以使用随机化算法，每次随机选取一个基准值，以达到更平均的效果。同时，我们也要注意避免不必要的比较。

在数据量较小的时候，我们可考虑使用直接插入排序。

堆排序

如果有一个关键码的集合 $K = \left\{k_0,k_1,k_2,\cdots,k_{n-1}\right\}$，把它的所有元素按完全二叉树的顺序存储在一个一维数组中，并满足：$k_i k_{2i+1} $ 且 $k_i \leqslant K_{2i = 2}$，则称为小根堆（还有大根堆）。

下面只讨论小根堆。

堆有如下性质：

堆中某个节点不大于其父节点的值。
堆总是一颗完全二叉树（这也是我们能将其放入一个一维数组中的前提）。
堆以层序遍历的顺序存在数组中，有些文章不使用数组的第 $0$ 个元素，而从数组的第一个元素开始存，我这里从第 0 个元素开始存。
对于第 $i$ 个元素，其父节点的索引为 $\lfloor \frac{i - 1}{2}\rfloor$，左孩子的索引为 $2i + 1$，右孩子的索引为 $2i +2$.

堆的两个重要操作是向上调整算法和向下调整算法。

向下调整算法：

先设定根节点为当前节点（通过下标获取，标记为cur），比较左右子树的值，找出更小的值，用 child 来标记。
比较 child 和 cur 的值，如果 child 比 cur 小，则不满足小堆的规则，需要进行交换。
如果 child 比 cur 大，满足小堆的规则，不需要交换，调整结束。
处理完一个节点之后，从当前的 child 出发，循环之前的过程。

向下调整的代码：

void down(int *arr, int n, int cur) {
    // 左子树
    int child = 2 * cur + 1;
    while (child < n) {
        // 比较左右子树，找到较小值
        if (child + 1 < n && arr[child + 1] < arr[child]) {
            ++child;
            // child时刻保存较小值的下标
        }
        if (arr[child] < arr[cur]) {

            int tmp = arr[child];
            arr[child] = arr[cur];
            arr[cur] = tmp;

            cur = child;
            child = 2 * cur + 1;
        } else {
            break;
        }
    }
}

向上调整算法：

先设定倒数的第一个叶子节点为当前节点（通过下标获取，标记为cur），找出他的父亲节点，用 parent 来标记。
比较 parent 和 cur 的值，如果 cur 比 parent 小，则不满足小堆的规则，需要进行交换。
如果 cur 比 parent 大，满足小堆的规则，不需要交换，调整结束。
处理完一个节点之后，从当前的 parent 出发，循环之前的过程。

向上调整的代码：

void up(int *arr, int n, int cur) {
    int parent = (cur - 1) / 2;
    while (cur > 0) {
        if (arr[cur] < arr[parent]) {

            int tmp = arr[cur];
            arr[cur] = arr[parent];
            arr[parent] = tmp;

            cur = parent;
            parent = (cur - 1) / 2;
        } else {
            break;
        }
    }
}

堆的插入是将数据插入到数组最后，做一次 up() 操作；删除堆的数据是删除堆顶的数据，先将堆顶元素与最后一个元素交换，将数组最后一个元素删除，然后堆堆顶元素做一次 down() 操作。

堆排序就是将将数据存储到堆里，然后将一一拿出堆顶的元素，就可以完成排序。

完整代码如下：

                                      #include <iostream>

using namespace std;

void down(int *arr, int n, int cur) {
    // 左子树
    int child = 2 * cur + 1;
    while (child < n) {
        // 比较左右子树，找到较小值
        if (child + 1 < n && arr[child + 1] < arr[child]) {
            ++child;
            // child时刻保存较小值的下标
        }
        if (arr[child] < arr[cur]) {

            int tmp = arr[child];
            arr[child] = arr[cur];
            arr[cur] = tmp;

            cur = child;
            child = 2 * cur + 1;
        } else {
            break;
        }
    }
}

void up(int *arr, int n, int cur) {
    int parent = (cur - 1) / 2;
    while (cur > 0) {
        if (arr[cur] < arr[parent]) {

            int tmp = arr[cur];
            arr[cur] = arr[parent];
            arr[parent] = tmp;

            cur = parent;
            parent = (cur - 1) / 2;
        } else {
            break;
        }
    }
}

void heapify(int arr[], int n) {
    for (int i = n / 2; i >= 0; --i) {
        down(arr, n, i);
    }
}

void heap_sort(int arr[], int n) {
    int end = n - 1;
    while (end > 0) {
        
        int tmp = arr[0];
        arr[0] = arr[end];
        arr[end] = tmp;

        down(arr, end, 0);
        end--;
    }
}
int main() {
    int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7,
                 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
    int len = (int)sizeof(arr) / sizeof(*arr);
    heapify(arr, len);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

注意：这里使用的是小根堆进行原地排序，所以排序结果是逆序的，如果想要正序的结果，请使用辅助空间、大根堆或者排序之后进行逆序。

显然，堆排序的时间复杂度为 $\Omicron \left(n \log n \right)$.

排序算法概述

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

参考