『算法导论』第 8 章：线性时间排序

本章介绍几种线性时间复杂度的 排序 算法。我们前面介绍的 排序算法 都是通过比较元素大小来确定排序顺序的，本章介绍的算法通过运算来确定排序顺序。

排序算法的下界

比较排序可以抽象成一颗决策树。 决策树 是一颗完全二叉树，它可以表示在给定输入规模情况下，某一特定算法对所有元素的比较操作。

通过决策树模型我们可以证明，在最坏情况下，任何比较排序算法都要做$\Omega(n \lg n)$次比较。也就是说，归并排序和堆排序都是渐进最优的，而且，任何已知的比较排序算法最多就是在常数因子上优于它们。

计数排序

计数排序（counting sort）假设$n$个元素中每一个都是在$0$到$k$区间内的一个整数，其中$k$为某个整数。计数排序的基本思想是：对于每一个输入元素，确定小于它的元素的个数。利用这一信息，就可以直接把它放到输出数组中的位置上。

在计数排序算法的代码实现中，假设输入是数组$A[1…n]$，我们还需要两个数组：$B[1…n]$存放排序的输出，$C[0…k]$提供临时存储空间。下面是实现代码：

void CountingSort(int A[], int B[], int n, int k)
{
    int *C = malloc((k+1)*sizeof(int));
    for (int i = 0; i < k+1; i++) {
        C[i] = 0;
    }
    for (int j = 0; j < n; j++) {
        C[A[j]]++;
    }
    // C[i]现在包含等于i的元素的个数
    
    for (int i = 1; i < k+1; i++) {
        C[i] = C[i] + C[i-1];
    }
    // C[i]现在包含小于等于i的元素的个数
    
    for (int j = n-1; j >= 0; j--) {
        B[C[A[j]]-1] = A[j];    // 如果有m个元素小于等于A[j]，将它放在数组第m个位置
        C[A[j]] = C[A[j]] - 1;  // 处理有相同元素的情况
    }

    free(C);
}

很容易分析得到，当$k=O(n)$时，计数排序的运行时间为$\Theta(n)$。它的代码中完全没有输入元素之间的比较操作，用输入元素的实际值来确定其在数组中的位置。计数排序的一个重要特征是它是 稳定的 ：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的相对次序相同。计数排序经常用于基数排序算法的一个子过程，正因为它是稳定的。

基数排序

基数排序（radix sort）是一种用在卡片排序机上的算法。基数排序从最低有效位到最高有效位依次排序每一个位。为了确保正确性，一位数排序算法必须是稳定的，可以选择上述的计数排序。

基数排序的思想很简单，代码从略。可以证明，给定$n$个$d$位数，其中每个数有$k$个可能的取值，如果基数排序使用的稳定排序方法耗时$\Theta(n+k)$，那么它可以在$\Theta(d(n+k)$时间内将这些数排好序。

桶排序

桶排序（bucket sort）假设输入数据服从均匀分布，平均情况下它的时间代价为$O(n)$。与计数排序类似，因为对数据作了某种假设，桶排序的速度也很快。桶排序假设输入是由一个随机过程产生，元素均匀分布在$[0,1)$区间上。

桶排序将$[0,1)$区间划分为$n$个相同大小的子区间，称之为 桶 。然后将$n$个输入数分别放到各个桶中。由于分布是均匀的，一般不会出现很多落在同一个桶中的情况。为了得到输出结果，先对每个桶中的数进行排序（比如使用插入排序算法），然后遍历每个桶，按照次序把各个桶中的元素列出来即可。

代码实现需要用到链表，代码从略。可以分析得到，桶排序的期望运行时间为$\Theta(n)$。即使输入数据不服从均匀分布，只要输入数据满足下列性质：所有桶的大小的平方和与总的元素个数呈线性关系，桶排序就能在线性时间完成。