【算法导论】线性时间排序（计数排序、基数排序、桶排序）

引言：
  在排序的最终结果中，各元素的次序依赖于它们之间的比较，我们把这类排序算法称为比较排序，对于包含n个元素的输入序列来说，任何比较排序在最坏情况下都要经过 $\Omega (nlgn)$次比较，下面将讨论三种线性时间复杂度的排序算法。

1.排序算法的下界

  比较排序可以被抽象为一棵决策树，以下是作用于三个元素时的比较排序决策树：

  在决策树中，，每个内部节点都以 $i:j$ 标记，其中，i 和 j 满足 $1\le i,j\le n$，n 是输入序列中的元素个数，每个叶节点上都标注一个序列 $<\pi (1)，\pi (2)，...,\pi (n)>$，排序算法的执行对应于一条从树的根节点到叶结点的路径。每一个内部节点表示一次比较 $a_i\le a_j$。左子树表示一旦我们确定 $a_i\le a_j$之后的后续比较，右子树表示在确定了$a_i>a_j$的后续比较。当到达叶节点时，表示排序算法已经确定了一个顺序$a_{\pi (1)}\le a_{\pi (2)}\le ...\le a_{\pi (n)}$。
  在决策树中，从根节点到任意可达叶节点之间的最长简单路径的长度，表示的是对应排序算法中最坏情况下的比较次数。因此，一个比较排序算法中最坏情况比较次数就等于决策树的高度。
  对于正确的比较排序算法来说，n 个元素的 n！种可能的排列都应该出现在决策树的叶结点上。在一棵高为 h 、具有 l 个可达叶结点的决策树中，输入数据的 n！中可能的排列都是叶节点，所以有 $n!\le l$ 。由于二叉树的高为h，叶结点的数目不多于 $2^h$，我们可以得到：$$n!\le l\le 2^h$$对该式两边取对数有 h ≥ l g ( n ! ) = Ω ( n l g n ) h≥lg(n!)=Ω(nlgn)

h​≥lg(n!)=Ω(nlgn)​ 由此，我们可以得到比较排序算法中的最坏情况比较时间复杂度至少为 $nlgn$

2.计数排序

计数排序的要求： n个输入元素中的每一个都是在 0 到 k 之间的整数，其中 k 为某个整数。

计数排序的基本思路： 对于每一个输入的元素x，确定小于 x 的元素的个数。利用这一信息，我们可以直接把 x 放到它在输出数组中的位置上。

计数排序算法可视化：

1. 统计数组A中 0 到 k 元素出现的个数，A数组中元素 i 的个数存放在 C 数组下标 i 的位置。
   
2. 对数组 C 进行前缀和处理。
   
3. 将数组A中的值倒序遍历按照其在映射到 C 数组中对应的下标位置idx，找到其元素值 val ，存放在 B 数组的相应位置，存放完成后，将 val 的值减一。
   
4. 重复过程三，遍历数组 A ，完成排序。

计数排序伪代码：
  假设输入是一个数组 A[ 1…n ]，A.length = n，B[ 1…n ]数组存放排序的输出，C[ 1…n ]提供临时存储空间。

	COUNT—SORT(A,B,k)
		// 初始化备用数组，将其 0 到 k 之间的下标元素都置为 0
		let i = 0 to k
			C[i] = 0
		// 统计元素值为 A[j] 的元素个数，A[j]作为下标，C[A[j]]作为A[j]的个数
		for j = 1 to A.length
			C[A[j]] = C[A[j]] + 1
		// 从 1 到 k 进行前缀和处理，统计比i小的元素有几个
		for i = 1 to k
			C[i] = C[i] + C[i-1]
		// 将A数组从后向前遍历（保证其稳定），是每一个元素插入相应的位置。
		for j = A.length downto 1
			B[C[A[j]]] = A[j]
			C[A[j] = C[A[j] - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

C++实现计数排序：

• 头文件：

#include   
#include   
#include  
1
2
3

• 调用与传参：

vector<int> A = { 4, 2, 2, 8, 3, 3, 1, 12, 56, 47 };
auto max_num_iter = max_element(A.begin(), A.end());
Counting_Sort(A,*max_num_iter);
1
2
3

• 函数：

void Counting_Sort(vector<int>& A, int max_value) {
    // 创建计数数组，用于存储每个数字出现的次数  
    vector<int> C(max_value + 1, 0);

    // 统计每个数字出现的次数  
    for (int i = 0; i < A.size(); i++) {
        C[A[i]]++;
    }

    // 求前缀和
    for (int i = 1; i <= max_value; i++) {
        C[i] += C[i - 1];
    }

    // 创建临时数组，用于存储排序后的数字序列  
    vector<int> B(A.size());

    // 从后向前遍历原始数组，将数字按照计数数组中的顺序放入临时数组中  
    for (int i = A.size() - 1; i >= 0; i--) {
        B[--C[A[i]]] = A[i];
    }

    // 将临时数组中的数字复制回原始数组  
    for (int i = 0; i < A.size(); i++) {
        A[i] = B[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

计数排序时间复杂度分析： 第一个循环所花的时间为 $\theta (k)$，第二个循环所花的时间为 $\theta (n)$，第三个循环所花的时间为 $\theta (k)$，第四个循环所花的时间为 $\theta (n)$，所以，总的时间代价为 $\theta (k+n)$，在实际工作中（例如对高考成绩排序），当 $k=O(n)$ 时，我们会采用计数排序，这样运行时间为 $O(n)$。

3.基数排序

基数排序的要求： 只能针对整数进行排序。

基数排序的基本思路： 针对输入数组元素中的每一个数，按照从低位（个位）到高位的方法，利用稳定的排序算法进行排序。

基数排序算法可视化：

基数排序伪代码：

RADIX-SORT(A,d)
	for i = 1 to d
		use a stable sort to sort array A on digit i
1
2
3

C++实现基数排序：

• 头文件：

#include   
#include   
1
2

• 调用与传参：

vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66};
Radix_Sort(arr);
1
2

• 函数：

 void Radix_Sort(vector<int>& arr) {
    // 找到数组中的最大值  
    int max_num = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
    }

    // 从最低位开始，按照每个数字的位数进行排序  
    int exp = 1; // 当前位数  
    while (max_num / exp > 0) {
        // 创建桶数组，用于存储当前位数的数字计数  
        vector<int> bucket(10, 0);
        for (int i = 0; i < arr.size(); i++) {
            // 将当前数字放入对应的桶中  
            bucket[(arr[i] / exp) % 10]++;
        }
        // 将桶中的计数转换为累计计数，方便后续放入数字  
        for (int i = 1; i < 10; i++) {
            bucket[i] += bucket[i - 1];
        }
        // 创建临时数组，用于存储排序后的数字序列  
        vector<int> temp(arr.size());
        // 从后向前遍历原始数组，将数字按照当前位数放入对应的桶中  
        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[--bucket[(arr[i] / exp) % 10]] = arr[i];
        }
        // 将临时数组中的数字复制回原始数组  
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = temp[i];
        }
        // 更新当前位数  
        exp *= 10;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

基数排序时间复杂度分析：

• 引理1：给定 n 个 d 位数，其中每一个数位有 k 个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时 $\theta (n+k)$，那么它就可以在 $\theta (d\ast (n+k))$ 时间内将这些数排好序。
• 引理2：给定 n 个 b 位二进制数和任何整数 $r\le b$，如果RADIX-SORT使用的稳定排序算法对数据取值区间是 0 到 k 的输入进行排序耗时 $\theta (n+k)$，那么它就可以在 $\theta ((b/r)(n+2^r))$时间内将这些数据排好序。

4.桶排序

桶排序的要求： 输入数据服从均匀分布，元素取值在 [0,1) 之间。

桶排序的基本思路： 桶排序将 [0,1) 区间划分为 n 个相同大小的子区间，或称为桶。然后，将 n 个输入数分别放到各个桶中。因为输入数据是均匀、独立分布在 [0,1) 区间上，所以一般不会出现很多数落在一个区间的情况。为了得到输出结果，我们先对每个桶中的数进行排序，然后遍历每一个桶，按照次序把各个桶中的元素列出来即可。

桶排序算法可视化：

桶排序伪代码：

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

C++实现桶排序：

• 头文件：

# include   
# include 
# include   
# include 
1
2
3
4

• 调用与传参：

vector<float> A = { 0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68 };
Bucket_Sort(A);
1
2

• 函数：

void Bucket_Sort(vector<float>& A) {
    int n = A.size();
    // Step 1: 初始化桶数组 B  
    vector<vector<float>> B(n);
    // Step 2: 将元素插入到对应的桶中  
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * A[i]; // 计算元素应进入哪个桶  
        B[bucketIndex].push_back(A[i]);
    }
    // Step 3: 对每个桶中的元素进行排序，这里使用插入排序  
    for (int i = 0; i < n; i++) {
        sort(B[i].begin(), B[i].end());
    }
    // Step 4: 将排序后的桶合并到一起  
    int index = 0; // 用于跟踪合并后的数组中的下一个空位置  
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < B[i].size(); j++) {
            A[index++] = B[i][j];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

桶排序时间复杂度分析：
  假设 $n_i$ 表示桶 B[i] 中元素个数的随机变量，因为插入排序的的时间是平方阶的，索引桶排序的时间代价为：$$T(n)=\theta (n)+\sum _{i=1}^{n-1}O(n_i^2)$$

  对上式两边取期望，并利用期望的线性性质得到： E [ T ( n ) ] = E [ θ ( n ) + ∑ i = 1 n − 1 O ( n i 2 ) ] = θ ( n ) + ∑ i = 1 n − 1 E [ O ( n i 2 ) ] = θ ( n ) + ∑ i = 1 n − 1 O E [ ( n i 2 ) ] E[T(n)]=E[θ(n)+n−1∑i=1O(n2i)]=θ(n)+n−1∑i=1E[O(n2i)]=θ(n)+n−1∑i=1OE[(n2i)]

E[T(n)]​=E[θ(n)+i=1∑n−1​O(ni2​)]=θ(n)+i=1∑n−1​E[O(ni2​)]=θ(n)+i=1∑n−1​OE[(ni2​)]​

  因为输入数组 A 的每一个元素是等概率的落入任意一个桶中，所以每个桶 i 具有相同的期望值 $E[n_i^2]$，我们定义随机变量：对所有 i = 0，1，…，n-1 和 j = 1，2，…，n， X i j = I { A [ j ] 落入桶 i } X_{ij}=I \{ A[j]落入桶 i \} Xij​=I{A[j]落入桶i}

  因此有：$$n_i=\sum _{j=1}^n{X}_{ij}$$

  为了计算 $E[n_i^2]$ ，我们展开平方项，并重新组合各项：
E [ n i 2 ] = E [ ( ∑ j = 1 n X i j ) 2 ] = E [ ∑ j = 1 n ∑ k = 1 n X i j X i k ] = E [ ∑ j = 1 n X i j 2 + ∑ j = 1 n ∑ k = 1 , k ≠ j n X i j X i k ] = ∑ j = 1 n E [ X i j 2 ] + ∑ j = 1 n ∑ k = 1 , k ≠ j n E [ X i j X i k ] E[n2i]=E[(n∑j=1Xij)2]=E[n∑j=1n∑k=1XijXik]=E[n∑j=1X2ij+n∑j=1n∑k=1,k≠jXijXik]=n∑j=1E[X2ij]+n∑j=1n∑k=1,k≠jE[XijXik]

E[ni2​]​=E[(j=1∑n​Xij​)2]=E[j=1∑n​k=1∑n​Xij​Xik​]=E[j=1∑n​Xij2​+j=1∑n​k=1,k=j∑n​Xij​Xik​]=j=1∑n​E[Xij2​]+j=1∑n​k=1,k=j∑n​E[Xij​Xik​]​

  接下来我们计算最后的两项，$X_{ij}$ 为 1 的概率为$\frac{1}{n}$ ，其他情况都是 0，于是有：$$E[X_{ij}^2]=1^2\ast \frac{1}{n}+0^2\ast (1-\frac{1}{n})=\frac{1}{n}$$

  当 $k\ne j$时，随机变量$X_{ij}和X_{ik}$是独立的，因此有：
$$E[X_{ij}{X}_{ik}]=E[X_{ij}]E[X_{ik}]=\frac{1}{n}\ast \frac{1}{n}=\frac{1}{n^2}$$

  将这两个期望值代入公式得到：
E [ n i 2 ] = ∑ j = 1 n 1 n + ∑ j = 1 n ∑ k = 1 , k ≠ j n 1 n 2 = n ∗ 1 n + n ( n − 1 ) ∗ 1 n 2 = 1 + n − 1 n = 2 − 1 n E[n2i]=n∑j=11n+n∑j=1n∑k=1,k≠j1n2=n∗1n+n(n−1)∗1n2=1+n−1n=2−1n

E[ni2​]​=j=1∑n​n1​+j=1∑n​k=1,k=j∑n​n21​=n∗n1​+n(n−1)∗n21​=1+nn−1​=2−n1​​

  最终我们可以得到结论，桶排序的期望运行时间为：$$\theta (n)+n\ast O(2-1/n)=\theta (n)$$
  即使输入数据不服从均匀分布，只要输入的数据满足：所有的桶的大小的平方和与总的元素的个数呈线性关系，那么桶排序仍能在线性时间内完成。