前言#

好久没有更新，最近忙于复习周前的各种quiz和ddl，终于到了复习周可以好好复习更新了。这一章是关于线性时间内的排序的算法分析。

比较排序的下界证明#

首先我们知道， 决策树(decision tree): 是一棵 满二叉树(full binary tree) （每个结点要不没有孩子结点，要不有两个孩子结点），用来表示对给定规模的输入序列执行特定的排序算法过程中的元素比较。例如下面是一个比较三个元素的决策树：

接着我们回顾之前的比较排序算法，它们最低的时间复杂度也需要 $\Theta(n\lg n)$ ，下面是证明：

设决策树高度为h，叶结点个数为l，此时可以知道 $l \leq 2^h$ 因为如上图所示，h高度为从决策树根结点到可达叶结点的最长简单路径的长度。对于n个变量的问题，这n个变量有n!种可能的顺序（如上图3个变量排序，有3! = 6种可能）。因此， $n! \leq l \leq 2^h \rightarrow 2^h \geq n \rightarrow h \geq \lg(n!)$ 。根据Sterling 近似公式，有 $n! \approx \sqrt{2\pi n}(n/e)^n \Rightarrow n! > (n/e)^n$ 带入可得， $h \geq \lg(n/e)^n = n \lg(n/e) = n \lg n - n \lg e = \Omega(n \lg n)$

计数排序#

计数排序的思想非常简单，对于一个数组A[1]里有多个重复数据的时候，使用空间换取时间的策略。设输出序列为B[1]，临时存储空间为C[0] (k是数据中的最大值)，C用来存储A中每一个元素存放的次数。计数排序的步骤为：

遍历数组A，统计A中当前数据出现的次数，并且该数据作为索引，出现次数存在C中。
从0开始，累加数组C（ $C_i += C_{i-1}$ ），用于定位该数据在输出中的最后位置。
反向遍历A，查找A[j]数据在C中的数据，它记录着A[j]数据的最后位置，并在B中的对应位置（对应C中存的地址数据）放上数据A[j]，接下来C[A[j]]—，继续遍历A的下一位直到结束。
输出B为答案。

1
COUNTING-SORT(A, n, k)
2
    let B[1:n], C[0:k] be new arrays
3
    for i = 0 to k
4
        C[i] = 0
5
    for j = 1 to n
6
        C[A[j]] = C[A[j]] + 1
7
    // C[i] now contains the number of elements equal to i.
8
    for i = 1 to k
9
        C[i] = C[i] + C[i - 1]
10
    // C[i] now contains the number of elements less than or equal to i.
11
    // Copy A to B, starting from the end of A
12
    for j = n downto 1
13
        B[C[A[j]]] = A[j]
14
        C[A[j]] = C[A[j]] - 1 // to handle duplicate values

举例说明：例如A[NUL,2,5,3,0,2,3,0,3] （从1开始，第0为未知设置为NUL），则按照上面的步骤：

C的大小为[0:5]，因为5为数据中最大的数，C的统计初始值为：[2,0,2,3,0,1]，如图中(a)
遍历并累加数组C，确定数据A[i]在输出B中的最后位置，累加后C的值为：[2,2,4,7,7,8]。这里演示一小部分：
1. C[1] += C[0] = 2，此时数据1在输出中的最后地址为2，但是与数据0相同，所以数据1不存在。
2. C[2] +=C[1] = 4，此时数据2在输出中的最后地址为4，此时相当于从上一个地址开始，有2位是数据2的。
3. 以此类推，如图中(b)…
反向遍历A，查找A[j]数据在B的最后位置（存于C[A[j]]中），并给那个位置放上数据A[j]。从尾部开始，先是数据3，找到C[3]的最后位置为7，那么第一个3就被放到第7位上（B与A一样从1开始），同时C[3]—得6（如图(c)）。接下来到数据0，找到C[0]的最后位置为2，把一个0放到B的第2位上，同时C[0]— = 1（如图(d)）。依次类推（如图(e)）……
最后得到B为[0,0,2,2,3,3,3,5]（如图(f)）

综上所述，计数排序适用于对一个数组中存在重复元素的情况进行排序，很明显，它的时间复杂度为 $\Theta(n + k)$ 。对于计数排序中，我们C中存的是该数据的最末地址，而我们也是从末位开始遍历原数组A，故同数据的排序前后顺序不变，是个稳定的(stable)排序。

对于稳定性，这里需要拓展一个概念——卫星数据(Satellite Data)，它是除了需要排序的主要关键字之外的其他关联数据。例如：一个结构Stu中，有两个属性：id和score，学生1的数据为s1.id = 001, s1.score = 99; 学生2的数据为s2.id = 002, s2.score = 99. 设score为需要排序的关键字，那么此时id就是卫星数据。

对于讨论一个排序算法的稳定性，它要求如果两个记录有相同的主键，则它们在排序后的顺序仍与排序前的顺序一致。即要求， 它们排序之后卫星数据的顺序不变 。

此外，我们已经学习过的具有稳定性的排序有 插入排序，冒泡排序，归并排序等 。

我们知道上述代码中，我们新建了一个B数组，会使得空间复杂度变为O(n)，如果设由n个元素组成的输入序列每个元素都是区间[0]内的一个整数，且这些元素没有卫星数据，修改COUNTING-SORT，只用数组A和C，将输出序列放在A中。

1
COUNTING-SORT(A, n, k)
2
    let C[0:k] be new arrays
3
    for i = 0 to k
4
        C[i] = 0
5
    for j = 1 to n
6
        C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i.
7
    p = 1
8
    for i = 0 to k
9
        while C[i] > 0
10
            A[p] = i
11
            p = p + 1
12
            C[i] = C[i] - 1

此时修改的部分有：

第二步此时C记录的是数据A[j]在输出时的 最初位置（故C[A[j]] + 1）。
输出的时候 需要从头遍历数组 ，因为此时为最初位置。用一个变量p记录输出到A中的索引值。

基数排序#

对于基数排序，是将数据按照基数的顺序（0~9，x mod 10得到的）进行排序，再对基数内的数据进行排序的算法。实际上可以看成是桶排序的一种情况，这里就不过多讨论了，详情请见之后的桶排序和之前对于基数排序的介绍：

https://hoyue.fun/data_structure_hmk2.html#i-3

桶排序#

我们通过假设输入数据以分析桶排序。假设一组数据总体为X，X~U(0,1)，表示数据在区间[0,1)上满足均匀分布。桶排序将区间[0,1)分成n个大小相等的子区间，称这些子区间为 桶(bucket) 。

那么我们就设数据数组A[1]， $A[i]∈[0,1)$ ，再设一个数组 B[0]，用来表示桶，它使用链表进行维护。

那么桶排序的步骤为：

根据A数组新建B链表数组，并初始化为0。
将A数组中的元素依次按照一定的规则插入到桶中。（有点像散列表）。
对每个桶内部进行插入排序，当插入排序规模很小的时候，趋向于 $\Theta(n)$ 。
按顺序输出每个桶（桶设置时是有序的）。

对于上述这样的数据，我们可以写出这样的代码：

1
BUCKET-SORT(A, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        insert A[i] into list B[⌊n · A[i]⌋]
7
    for i = 0 to n - 1
8
        sort list B[i] with insertion sort
9
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
10
    return the concatenated lists