算法导论 5-线性时间排序

• 1. 决策树
• • a. 用决策树来表示排序算法的过程
  • b. 用决策树的表达方式比较排序算法
• 2. 线性时间排序
• • a. 计数排序（Counting Sort）
  • b. 基数排序（Radix Sort）

目前已知最好的排序算法是，随机算法，非常复杂，其时间复杂度为 Θ ( n l g l g n ) Theta(nsqrt {lglgn}) Θ(nlglgn ​)

1. 决策树

a. 用决策树来表示排序算法的过程

比较排序可以被抽象为一颗决策树（算法导论 P191）

例子： 对无序数组 < a 1 , a 2 , a 3 > 进行排序，可以得到如下决策树，图中1、2、3代表数组下标：

以根节点为例，若 a 1 < = a 2 a_{1}<=a_{2} a1​<=a2​，则走向二叉树左边；若 a 1 > a 2 a_{1}>a_{2} a1​>a2​，则走向二叉树右边

定理：
若存在无序数组 A = < a 1 , a 2 , a 3 , a 4 , . . . , a n > A= A=，对数组 A A A进行排序，需要对数组中的元素 a i a_i ai​和 a j a_j aj​进行比较；如此可生成一棵树，左边子树对比 a i < = a j a_i<=a_j ai​<=aj​，右边子树比应该 a i > a j a_i>a_j ai​>aj​，每一个叶节点表示一次比较（排序）

b. 用决策树的表达方式比较排序算法

为一个 n n n维数组绘制一颗决策树，决策树列出了算法的所有可能结果

证明： 决策树深度的最小值是 n l o g n nlogn nlogn
已知条件：决策树中的叶节点个数为 n ! n! n!（数组中所有数的全排列），证明过程如下：
         设树的深度为 h h h，则:
                 2 h > = n ! 2^{h} >= n! 2h>=n!
         两边同时取对数，得到：
                 h > = l o g n ! h >= log n! h>=logn!
        且已知（斯特林公式）：
                 n ! > = ( n / e ) n n!>=(n/e)^n n!>=(n/e)n
                 l o g n ! = ( l o g n + l o g ( n − 1 ) + l o g ( n − 2 ) + . . . + l o g 2 + l o g 1 ) > = l g ( n / e ) n logn!=(logn+log(n-1)+log(n-2)+...+log2+log1)>=lg(n/e)^n logn!=(logn+log(n−1)+log(n−2)+...+log2+log1)>=lg(n/e)n
        由此得到：
                 h > = l o g n ! > = n l o g ( n / e ) = n l o g ( n / e ) h>=logn!>=nlog(n/e)=nlog(n/e) h>=logn!>=nlog(n/e)=nlog(n/e)

比较类排序算法，所用排序时间的下届就是决策树的深度。由此可知，归并排序和堆排序是监禁最优的，依赖于 n n n

2. 线性时间排序

由上面决策树高度可知，比较模型的时间在 n l o g n nlogn nlogn，下面介绍两个线性时间排序算法

a. 计数排序（Counting Sort）

输入: A [ 1 , 2 , 3 , . . . , n ] A[1, 2,3,...,n] A[1,2,3,...,n]，其中 A [ i ] ∈ { 1 , . . . , K } A[i]{in}{1,...,K} A[i]∈{1,...,K}，即 A [ i ] A[i] A[i]为 1 1 1到 K K K之间的整数
输出: A A A的排序序列

计数排序代码如下，升序排序：

# 定义一个长度为K的数组
C = [0 for _ in range(K+1)] 
B = [0 for _ in range(len(A))]

#计算出A中等于i的元素个数
for i in range(len(A)):
	C[A[i]] += 1
	
#计算出A中小于i的元素个数
for j in range(1, K+1):
	C[j] += C[j-1]

for i in range(len(A), -1):
	B[C[A[i]-1] = A[i]
	C[A[i]] -= 1

例子： A = [ 4 , 1 , 3 , 4 , 3 ] A=[4,1,3,4,3] A=[4,1,3,4,3]， C = [ 0 , 0 , 0 , 0 , 0 ] C=[0,0,0,0,0] C=[0,0,0,0,0]
        第一步，计算 C C C
                 C = [ 0 , 1 , 0 , 2 , 2 ] C=[0,1,0,2,2] C=[0,1,0,2,2]
                 C = [ 0 , 1 , 1 , 3 , 5 ] C=[0,1,1,3,5] C=[0,1,1,3,5]
      第二步，计算 B B B
                 B = [ 0 , 0 , 3 , 0 , 0 ] B=[0, 0,3,0,0] B=[0,0,3,0,0]
                 C = [ 0 , 1 , 1 , 2 , 5 ] C=[0,1,1,2,5] C=[0,1,1,2,5]

                 B = [ 0 , 0 , 3 , 0 , 4 ] B=[0,0,3,0,4] B=[0,0,3,0,4]
                 C = [ 0 , 1 , 1 , 2 , 4 ] C=[0,1,1,2,4] C=[0,1,1,2,4]

总结：
计数排序的时间复杂度为： Θ ( n + k ) Theta(n+k) Θ(n+k)，其需要额外的大小为 k k k的存储空间；
计数排序的时间复杂度取决于 k k k，若 k < = n k<=n k<=n，时间复杂度为 Θ ( n ) Theta(n) Θ(n)；若 k = 2 n k=2^n k=2n
如果 k < n l o g n k

计数排序具有稳定性，一个稳定性算法保证了相等元素的相对顺序

计数排序对缓存要求比较多，在实际中，计数排序并不那么快

b. 基数排序（Radix Sort）

基数排序用来在线性时间内处理大规模数据，基本思想是先对最后一位排序，按位排序，从最低为到最高位，每一位的排序需要有一个稳定性算法来进行排序

例子：
有如下数组：

• 3 2 9
• 4 5 7
• 6 5 7
• 8 3 9
• 4 3 6
• 7 2 0
• 3 5 5

1）先对个位进行排序，若遇到相等的数，总是保持其相对位置，可得到如下数组

• 7 2 0
• 3 5 5
• 4 3 6
• 4 5 7
• 6 5 7
• 3 2 9
• 8 3 9

2）对十位进行排序，得到如下数组：

• 7 2 0
• 3 2 9
• 4 3 6
• 8 3 9
• 3 5 5
• 4 5 7
• 6 5 7

3）对百位进行排序，得到如下数组：

• 3 2 9
• 3 5 5
• 4 3 6
• 4 5 7
• 6 5 7
• 7 2 0
• 8 3 9

证明：
      正确性
对已经排序的数字位进行归纳， t t t位
通过归纳假设，在 t t t之前的位已经排好序， t − 1 t-1 t−1位
对第 t t t位进行排序，有两种情况：

• 如果两元素相同，相对位置不变（稳定性），保持原序
• 如果两元素不同，那么调整其得到正确位置

利用计数排序作为辅助算法，假设有 n n n个整数，每个整数有 b b b bits（二进制整数设为 b b b比特长，取值范围在 0 0 0~ 2 b − 1 2^{b} -1 2b−1），把每个整数拆成 b / r b/r b/r位数字，每个是 r r r比特长，基于 2 r 2^r 2r进制来表示这个数（相对于二进制、十进制），每位数的范围在 0 0 0~ 2 r 2^r 2r间，一共有 b / r b/r b/r轮， K K K值为 2 r 2^r 2r。

时间复杂度
Θ [ ( b / r ) ∗ ( n + 2 r ) ] Theta[(b/r)*(n+2^r)] Θ[(b/r)∗(n+2r)]
对r求导，导为零的时候驻点，函数最小，此时 r = l o g n r=logn r=logn
因此，运行时间上界为 Θ ( b ⋅ n / l o g n ) Theta(b·n/logn) Θ(b⋅n/logn)，只要 b < l o g n b