常用的排序算法

在冒泡排序、选择排序和插入排序等基础排序算法暴露出性能问题之后，计算机科学家们对排序算法进行了深入探索和研究，以期改进算法。从1950年代末，各种更加高效的排序算法逐渐被提出。比如1959年，Donald Shell 提出的希尔排序（Shell Sort），它是插入排序的改进版本。插入排序的有序部分和无序部分紧挨着的，希尔排序通过加入一个间隔的概念，将待排序数组从逻辑上拆分成几个部分，然后逐步减小间隔进行排序，时间复杂度取决于间隔序列，一般为 $O(n^{1.3})$ 到 $O(n^{1.5})$。

简单的排序算法一般都比较符合人的直觉，但是性能不行，这些算法的时间复杂度通常为 $O(n^2)$。有效的排序算法时间复杂度为 $O(n \ log \ n)$，但通常不会那么直观，因为随着理论的研究，这些算法移除了低效算法做无用功的步骤。它们使用递归和分治这两个计算机科学的思想，这是有悖人类直觉的，要理解它们确实不是那么容易。不过，如果能慢慢习惯计算机这种思维方式，这些算法也就不难理解了。

归并排序

归并排序（Merge Sort）算法是冯·诺依曼在1945年提出的。它的基本思想将序列不断对半切分，直到所有子序列都只有一个元素。接着将子序列两两比较后合并到一个更大的有序序列，最终的大序列就是有序的序列。

让我们来看个例子，比如要排序的数组是：[6, 5, 3, 1, 8, 7, 2, 4]。

分割过程：

• 第一轮：对半分割成 [6, 5, 3, 1] 和 [8, 7, 2, 4]两个子序列。

• 第二轮：对每个子序列继续对半分割，切分成了 [6, 5]、[3, 1]、[8, 7]、[2, 4] 四个子序列。
• 第三轮：继续对子序列分割，切分成八个子序列：[6]、[5]、[3]、[1]、[8]、[7]、[2]、[4]。

子数组已经是最小了，不能再切分了，开始执行合并过程：

• 第一轮：[6] 与 [5]合并，[3] 与 [1] 合并，[8] 与 [7] 合并，[2] 与 [4] 合并，合并过程需要比较它们的大小，确保合并后的数组是有序的，合并成四个有序的数组：[5, 6]、[1, 3]、[7, 8]、[2, 4]。
• 第二轮：[5, 6] 与 [1, 3] 合并，[7, 8] 与 [2, 4] 合并。合并成两个有序数组数组：[1, 3, 5, 6] 和 [2， 4， 7， 8]。
• 第三轮：两个有序的子数组合并一个有序的最终数组：[1, 2, 3, 4, 5, 6, 7, 8]。

算法使用了分治法（Divide and Conquer），字面上的意思是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。

不断切分的过程很符合递归的思维，然后合并过程就是递归出栈过程。

#include <stdio.h>

// 合并 arr[] 的两个子数组
// 第一个子数组是 arr[left..mid]
// 第二个子数组是 arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int L[n1], R[n2];

    // 向临时数组 L[] 和 R[] 拷贝数据
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 将临时数组合并回 arr[left..right]
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝 L[] 剩余到数组 arr
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 拷贝 R[] 剩余到数组 arr
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// left 和 right 分别是 arr 子数组的左索引和右索引
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, 0, arr_size - 1);

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

归并排序在合并过程并不会打乱相等的元素，因此它是稳定的排序算法。

归并排序算法需要一个跟原序列相同大小的辅助序列用来存放中间结果，所以算法的空间复杂度是 $O(n)$。

时间复杂度有两个层面，一个是切分过程，另一个是合并过程。

切分过程：

在对半切分数组序列过程中，每一层递归切分的的数组，数量都是上一层的一半，当子序列只剩一个元素时，递归过程就结束了。也就是说，归并排序需要 $log \ n$ 次递归。

合并过程：

在递归的第一层，每个子序列元素数量最多有 $\frac n 2$ 个，共有 2 个序列，总共合并 1 次，n 个元素都会被比较一次，因此这一层的时间复杂度是 $O(n)$。

在递归的第二层，每个子序列元素数量最多有 $\frac n 4$ 个，共有 4 个序列，总共合并 2 次，n 个元素都会被比较至少一次，因此这一层的时间复杂度至少是 $O(n)$。

直至递归的最底层，每个子序列元素个数为 $\frac n n$，总共有 n 个序列，所有相邻的子序列两两合并，总共合并了 $\frac n 2$ 次，n 个元素都被至少比较一次，因此这一层的时间复杂度至少是 $O(n)$。

因此，每一次递归合并元素的时间复杂度至少是 $O(n)$，划分数组总共需要 $log \ n$ 次递归，因此，归并排序算法的时间复杂度至少是 $O(n \ log \ n)$。

归并排序最大的缺点是需要额外的空间来存储合并过程中的临时数据。对于大型数据集合，这可能成为一个问题。归并排序算法的最大优点可能就是稳定了，无论输入数据的初始顺序怎样，归并排序的时间复杂度始终为 $O(n \ log \ n)$，具有较好的性能保证。但在某些情况下，实际执行速度可能不如其它高效的排序算法，如快速排序。

快速排序

1959年，英国计算机科学家 Tony Hoare 提出了快速排序（Quick Sort）算法，它的基本思想是选择一个基准元素，将待排序的数据序列通过一趟比较拆分成两个子序列，比基准元素小的在左边，比基准元素大或等于基准元素的在右边。按同样的方法继续切分这两子序列，直至每个序列只有一个元素，最终这些单个元素的序列相互间必定是有序的。

我们选择第一个元素 p 作为基准元素：

接着从左往右扫描元素，小于 p 的元素位于左侧保持不动，如果遇上大于 p 的元素，则从右往左扫描，直到找到小于 p 的元素，和刚才左边大于 p 的元素交换位置：

不断持续这个过程，直到指示左右位置的两个游标指针 i 和 j 重合，整个数组就按照大于 p 和小于 p 划分好了。

最后，将 p 与小于 p 的最后一个元素交换位置，p 移到了中间，序列就这样被划分成小于 p 和大于 p 的左右两部分了：

对 <p 和 >p 的子序列不断重复以上步骤，数列便可排好序。

我们来看一个具体的例子，现在要对这个数组执行快速排序：[4, -1, -3, -4, 3, 7, -2, 9, 8, 0, 1, 5, 6, 2]。

用数组的第一个元素作为基准元素，对数组进行第一次分割：[-1, -3, -4, 3, -2, 0, 1, 2, (4), 7, 9, 8, 5, 6]。

将原来的数组序列一分为二之后，接下来对每一个子序列继续分割，可以用递归调用的方式来分割。左边的子序列选择第一个元素 -1 作为基准元素，右边的子序列选择第一个元素 7 作为基准。以此类推，详细的分割结果如下图所示。

上图展示的是每一次分割排序后的结果，其中每一层都被分割成了三部分（如果存在）：“左边｜基准元素｜右边”，它们全部按照“左边 < 基准元素 < 右边”顺序排列。将每一层中无法再分割的单个元素，这些单个元素之间相互之间是有序的，从左往右的连接起来便是我们需要的结果：[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[low]; // 选择第一个元素作为基准元素
        int i = low;
        int j = high;
        int temp;

        while (i <= j) {
            while (arr[i] < pivot) i++; // 将小于基准元素的元素移动至左边
            while (arr[j] > pivot) j--; // 将大于基准元素的元素移动至右边

            if (i <= j) { // 交换元素
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // 递归对两个分区排序
        if (low < j) quick_sort(arr, low, j);
        if (i < high) quick_sort(arr, i, high);
    }
}

在选取基准值时，如果下一个值和它是相等的，待最后将基准值交换到中间时，两个相等的元素顺序就被改变了，不管将相等值放在左边还是右边，都会产生类似的效果，因此快速排序是不稳定的排序。

基准元素的选择对于快速排序的性能至关重要，良好的基准元素能产生大致相等的两个子序列。对于一般的序列，元素分布比较均匀，足够随机，这时随便选择一个数组就能把数组分成两个大致相等的分区，每一次分区只需交换一半元素，总共需要分区 $log \ n$ 次，每一次需要交换的元素只有一半，即 ${\frac n 2} log \ n$ 次。每一次分区，所有元素都需要和基准元素比较一次，$log \ n$ 次分区后，总共需要比较 $n \ log \ n$ 次。因此，在一般情况下，快速排序算法的时间复杂度是 $\frac n 2 log \ n + n \ log \ n = O(n \ log \ n)$。

若使用递归，那么递归树的深度是 $log \ n$，空间复杂度也就是 $O(log \ n)$。

在极端的情况下，数组完全有序，不论是正序还是倒序，如果用最简单选取基准值的办法，比如选第一个或最后一个元素作为基准值，快速排序的时间复杂度会变成 $O(n^2)$。假设数组是完全正序的，选了第一个作为基准值，在第一次切分的时候，并不会交换任何数据，小于 p 的部分是空的。

后续只会对大于 p 的部分继续切分，但是一次递归只能处理一个元素，而且递归树的深度是 $n$ （准确地说是 $n-1$），总的比较次数是： $(n+(n-1)+(n-1) +...+1) \cdot 2 = n (n+1)=n^2+n$。因此，在极端情况下，如果数组已经完全有序了，快速排序的时间复杂度是 $O(n^2)$，空间复杂度是 $O(n)$。

为了避免出现这种最糟糕的情况，可以改进选择基准值的办法，比如可以随机选择，而不是选择两端的值。还可以使用三数取中法（Median-of-Three），选择第一个元素、中间元素和最后一个元素的中位数作为基准值，从而提高划分的平衡性，减少出现最坏情况的概率。

堆排序

随着业界对算法理论研究和改进，1964年，J. W. J. Williams 提出堆排序（Heap Sort）。堆排序使用了堆数据结构，可以从这篇文章了解堆数据结构。简单来说，堆在逻辑上是一种二叉树，但是它的底层是数组，在一维数组上实现二叉树的堆。

堆有大顶堆和小顶堆之分，大顶堆的最大值始终是数组的第一个元素，小顶堆的最小值始终是数组的第一个元素。在删除堆顶元素之后，堆的尾节点即数组的最后一个元素会被删掉，用来填补对顶，然后尾节点会被下沉到合适的位置，让它符合堆的数据结构。

如果我们不断删除堆顶元素，尾节点填补堆顶后，将堆顶元素放在空出来的尾节点位置。通过不断执行这个过程，元素就会从后往前有序排列，直到清空堆元素，整个数组就会变成有序列表，这便是堆排序的思想。大顶堆用来构建升序列表，小顶堆用来构建降序列表。

struct Heap<T> {
    data: Vec<T>
}

/// 堆排序实现
impl<T: Ord> Heap<T> {
    /// 堆排序
    fn sort(&mut self) {
        // 自底向上, 将数组转换成大顶堆
        for i in (0..self.data.len()).rev() {
            Self::max_heapify(&mut self.data, i);
        }

        // 将大顶堆最大值放到数组末尾，从尾到头逐个排列
        for i in (1..self.data.len()).rev() {
            self.data.swap(0, i);
            Self::max_heapify(&mut self.data[0..i], 0);
        }
    }

    /// 将根节点为 index 的子树转换成大顶堆
    fn max_heapify(array: &mut [T], index: usize) {
        let mut root = index;
        while let Some(child) = Self::max_child(array, root) {
            if array[child] > array[root] {
                array.swap(child, root);
            }
            root = child;
        }
    }

    /// 获取最大子节点 index
    fn max_child(array: &[T], parent: usize) -> Option<usize> {
        let left = parent * 2 + 1;
        let right = parent * 2 + 2;
        match (left >= array.len(), right >= array.len()) {
            (true, true) => None,
            (true, false) => Some(right),
            (false, true) => Some(left),
            (false, false) => match array[left] > array[right] {
                true => Some(left),
                false => Some(right),
            }
        }
    }
}

相等的元素相对顺序在构建堆的过程和删除对顶元素的时候可能会被改变，堆排序是不稳定排序。

由于堆排序是原地排序，只需要一个额外交换元素的空间，所以堆排序的空间复杂度是 $O(1)$。

如果要将数组应用堆排序，首先要将它转换成堆的结构。对于每一个元素，都需要对其子树做类似于删除堆顶元素后，将根节点下沉的比较，接着自下而上对每两层的父-子节点之间做比较。

堆是完全二叉树结构，完全二叉树下一层的元素数量是上一层两倍，如果层数是 h：

• 第$h - 0$层有$\frac n 2$个元素，需要比较0次。
• 第$h - 1$层有 $\frac n 4$个元素，需要比较1次。
• 第$h - 2$层有 $\frac n 8$个元素，需要比较2次。
• 第$h - 3$层有 $\frac n {16}$个元素，需要比较3次。
• ...
• 第1层有1个元素，需要比较$h-1$次。

完全二叉树的层数 $h$ 是 $log \ n$，加总之后的结果是 $n$，因此，构建堆的时间复杂度是 $O(n)$。

然后从堆中构建有序列表，删除对顶元素的时间复杂度是 $O(log \ n)$，总共需要删除 $n$ 次（准确地说是 $n-1$ 次），于是，删除所有堆顶元素是这样：$log \ n + log \ (n-1) + log \ (n-1) + … + log \ 1 = \sum_{k=1}^n log \ k$。利用对数的乘法性质将和转换为对数的积：$\sum_{k=1}^n log \ k = log \ ({1 \cdot 2 \cdot 3 … \cdot n)} = log \ n!$。通过特斯林公式得出：$log \ n! \approx \frac 1 2 log \ (2πn) + n \ log \ n - n$。舍弃低位，堆排序的时间复杂度是 $n \ log \ n$。

算法比较

本篇讨论的三个排序算法，它们各有特点：

它们有着相同的平均时间复杂度，归并排序需要与输入相等的额外空间存放中间结果，如果从空间经济性考虑，不如快速排序和堆排序那么完美，但是快速排序和堆排序也存在自己的问题。

比如在给多列数值的表格排序时，假设要给表格中的人排序，原来是按照名字字母顺序排列的，Alice 在 Bob 前面。现在要按照年龄排列，Alice 和 Bob 的年龄都是20，如果应用的时候不稳定的排序算法，Bob 很可能排在了 Alice 前面，因为不稳定的排序算法无法确保这一点，这可能不是我们期望的结果，有时候我们会希望不仅能按照年龄排序，如果年龄相同，还需要保持它们原有的顺序。

快速排序和堆排序无法满足稳定性要求，经过这两个算法排序后，对于两个相同元素原来的相对次序可能会被改变，可有时候我们希望维持他们原来的顺序，因此，排序算法的稳定性也是一个需要考量的重要因素。虽然归并排序需要与输入相等额外的辅助空间，但它是稳定的，归并排序仍有它存在的意义。

基准值的选择直接影响快速排序算法的性能，在极端情况下，时间复杂度会变成 $O(n)$，即使通过改进让它在最糟糕情况下达到 $O(n \ log \ n)$，但实际执行的效率确实有所下降。针对不同的数据特点，不同算法的实际执行效率也是有差别的，这三种排序算法各有千秋，接近理论最佳值的算法可能有多种，但有时候执行效率并不是唯一考量因素，就像上面提到的多列表格排序。因此说，并不存在一种算法绝对比另一种算法好，只是在考量的因素和边界条件下，某些算法比其它算法更合适罢了。

混合排序算法

归并排序、快速排序和堆排序出现已经大半个世纪了，至今仍在广泛使用，它们满足了今天大多情况下应用的要求。但是，这三种排序算法确实不能算是圆满，一种排序算法可能难以兼顾前面提到的多个维度的多种需求。比如使用最多的快速排序，其不能满足稳定性要求，在很多场景并不适用。如今，人们依然寻找更好的排序算法以适用某些特定的场景，不过，一种算法难以兼顾多个维度多种条件，但是，可以结合几种算法的思想，组合成一种混合排序算法（Hybrid Sorting Algorithm）针对不同的数据特点，自动选择算法类型。

比如说内省排序（Introsort），它是 David Musser 1997年设计的混合排序算法，它结合了快速排序、堆排序和插入排序的优点，确保在最坏情况下仍然有良好的性能。C++ 标准模板库（STL）中的std::sort函数就使用了内省排序。

在大多数情况下，内省排序使用快速排序，因为快速排序在平均情况下表现良好，时间复杂度是 $O(n \ log \ n)$，基准值的选择使用三数取中法，降低出现最坏情况的概率。但我们都知道快速排序的缺点，因此，当快速排序的递归深度超过某个阈值时（通常是$2 \ log \ n$），切换到堆排序，避免快速排序在最坏情况下时间复杂度降为 $O(n^2)$ 的情况，而堆排序的最坏情况时间复杂度仍能保持在 $O(n \ log \ n)$。如果数据规模很小，则使用插入排序，因为在小规模数据集情况下，插入排序的性能优于快速排序和堆排序。

蒂姆排序（Timsort）是另一个广泛使用的混合排序算法，它是 Tim Peters 在 2002 年为 Python 标准库设计的，后来 Java 7、Swift、Android 系统和 Chrome 浏览器等也使用了这个算法。蒂姆排序结合了归并排序和插入排序的优点。

假设我们安排了很多人随机排成一列，你会发现人的身高一高一矮交替出现的情况并不多，更多的是在一个区间里，身高总是递增的，或者递减的。即使用代码生成一个随机序列也会出现这种现象。蒂姆排序利用了数据序列这个分布特点，让我们看看它是怎么做的。

算法先通过遍历的办法，找出递增和递减的子序列，如果这样的话子序列太短，达不到预设的常数值（通常是32或64，这是为了利用缓存的局部性），则利用插入排序扩充子序列。插入排序在小规模数据集上的执行性能很好，而且在寻找插入位置的过程中使用了二分查找，也提升了性能。这些有序的子序列被放到堆栈中临时存储。

接下来就是合并这些子序列，先从最小的开始合并，而不是一长一短合并，这样效率会高些。从原理上讲，这和归并排序合并子序列是相同的。不过这个过程可以并行执行批量合并，而不是一个接着一个合并。

蒂姆排序的时间复杂度和归并排序是一样的，上限都是 $O(n \ log \ n)$，但在实际执行时，蒂姆排序比归并排序快几倍，可以使用随机序列测试，它和快速排序的性能是相当的。不同于快速排序（内省排序），蒂姆排序是一种稳定的排序算法，今天应用非常广泛。