算法导论第8章线性时间排序答案

怼烎@ 2022-05-14 03:26 209阅读 0赞

# 一、概念 #

## 1.比较排序 ##

比较排序是指通过输入元素间的比较来确定各元素次序的排序算法。

任何比较排序在最坏情况下都要用O(nlgn)次比较来进行排序

合并排序和堆排序是渐近最优的

## 2.非比较排序 ##

非比较排序指使用一些非比较的操作来确定排序顺序的排序算法

对于非比较排序，下界O(nlgn)不适用

计数排序是稳定排序，若n个数据的取值范围是\[0..k\]，则运行时间为O(n+k)，运行空间是O(n+k)

基数排序也是稳定排序，需要另一个稳定排序作为基础，若n个d位数，每一位有k种取值可能，所用的稳定排序运行时间为O(n+k)，则基数排序的时间是O(d(n+k))

桶排序也是稳定排序，当输入数据符合均匀分布时，桶排序可以以线性时间运行。所设所有元素均匀分布在区间\[0,1)上，把区间\[0,1)划分成n个相同大小的子区间（桶），对各个桶中的数进行排序，把依次把各桶中的元素列出来。

# 二、代码 #

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  \#include <iostream>   
2.  \#include <cmath>   
3.  using namespace std;  
4.    
5.  int length\_A, digit;  
6.    
7.  void Print(int \*A, int start, int end)  
8.  \{  
9.      int i;  
10.     for(i = start; i <= end; i++)  
11.     \{  
12.         if(i == start)cout<<'\{';  
13.         else cout<<' ';  
14.         cout<<A\[i\];  
15.     \}  
16.     cout<<'\}'<<endl;  
17. \}  
18.   
19. //计数排序   
20. void Counting\_Sort(int \*A, int \*B, int k)  
21. \{  
22.     int i, j;  
23.     //将C数组初始化为0，用于计数   
24.     int \*C = new int\[k+1\];  
25.     for(i = 0; i <= k; i++)  
26.         C\[i\] = 0;  
27.     //C\[j\]表示数字j在数组A中出现的次数    
28.     for(j = 1; j <= length\_A; j++)  
29.         C\[A\[j\]\]++;  
30.     //C\[i\]表示所以<=i的数字出现过的次数   
31.     for(i = 1; i <= k; i++)  
32.         C\[i\] = C\[i\] + C\[i-1\];  
33.     //初始化B为0，B用于输出排序结果    
34.     for(i = 1; i <= length\_A; i++)  
35.         B\[i\] = 0;  
36.     for(j = length\_A; j >= 1; j--)  
37.     \{  
38.         //如果<=A\[j\]的数字的个数是x,那么排序后A\[j\]应该出现在第x个位置，即B\[x\]=A\[j\]   
39.         B\[C\[A\[j\]\]\] = A\[j\];  
40.         C\[A\[j\]\]--;  
41.     \}  
42.     delete C;  
43. \}  
44. //基数排序调用的稳定排序   
45. void Stable\_Sort(int \*A, int \*B, int k, int d)  
46. \{  
47.     int i, j;  
48.     //将C数组初始化为0，用于计数   
49.     int \*C = new int\[k+1\];  
50.     for(i = 0; i <= k; i++)  
51.         C\[i\] = 0;  
52.     int \*D = new int\[length\_A+1\];  
53.     for(j = 1; j <= length\_A; j++)  
54.     \{  
55.         //D\[j\]表示第\[j\]个元素的第i位数字    
56.         D\[j\] = A\[j\] % (int)pow(10.0, d) / (int)pow(10.0, d-1);  
57.         //C\[j\]表示数字D\[j\]在数组A中出现的次数   
58.         C\[D\[j\]\]++;  
59.     \}  
60.     //C\[i\]表示所以<=i的数字出现过的次数   
61.     for(i = 1; i <= k; i++)  
62.         C\[i\] = C\[i\] + C\[i-1\];  
63.     //初始化B为0，B用于输出排序结果    
64.     for(i = 1; i <= length\_A; i++)  
65.         B\[i\] = 0;  
66.     for(j = length\_A; j >= 1; j--)  
67.     \{  
68.         //如果<=D\[j\]的数字的个数是x,那么排序后A\[j\]应该出现在第x个位置，即B\[x\]=A\[j\]   
69.         B\[C\[D\[j\]\]\] = A\[j\];  
70.         C\[D\[j\]\]--;  
71.     \}  
72.     delete \[\]C;  
73.     delete \[\]D;  
74. \}  
75. //基数排序   
76. void Radix\_Sort(int \*A, int \*B)  
77. \{  
78.     int i, j;  
79.     //依次对每一位进行排序，从低位到高位    
80.     for(i = 1; i <= digit; i++)  
81.     \{  
82.         Stable\_Sort(A, B, 9, i);  
83.         //输入的是A，输出的是B，再次排序时要把输出数据放入输出数据中   
84.         for(j = 1; j <= length\_A; j++)  
85.         A\[j\] = B\[j\];  
86.     \}  
87. \}  
88.   
89. int main()  
90. \{  
91.     cin>>length\_A>>digit;  
92.     int \*A = new int\[length\_A+1\];  
93.     int \*B = new int\[length\_A+1\];  
94.     int i;  
95.     //随机产生length\_A个digit位的数据    
96.     for(i = 1; i <= length\_A; i++)  
97.     \{  
98.         A\[i\] = 0;  
99.         while(A\[i\] < (int)pow(10.0, digit-1))  
100.             A\[i\] = rand() % (int)pow(10.0, digit);  
101.     \}  
102.     Print(A, 1, length\_A);  
103. //  Counting\_Sort(A, B, 9);    
104.     Radix\_Sort(A, B);  
105.     Print(A, 1, length\_A);  
106.     delete \[\]A;  
107.     delete \[\]B;  
108.     return 0;  
109. \}

#include <iostream>
    #include <cmath>
    using namespace std;
    
    int length_A, digit;
    
    void Print(int *A, int start, int end)
    {
    	int i;
    	for(i = start; i <= end; i++)
    	{
    		if(i == start)cout<<'{';
    		else cout<<' ';
    		cout<<A[i];
    	}
    	cout<<'}'<<endl;
    }
    
    //计数排序
    void Counting_Sort(int *A, int *B, int k)
    {
    	int i, j;
    	//将C数组初始化为0，用于计数
    	int *C = new int[k+1];
    	for(i = 0; i <= k; i++)
    		C[i] = 0;
    	//C[j]表示数字j在数组A中出现的次数
    	for(j = 1; j <= length_A; j++)
    		C[A[j]]++;
    	//C[i]表示所以<=i的数字出现过的次数
    	for(i = 1; i <= k; i++)
    		C[i] = C[i] + C[i-1];
    	//初始化B为0，B用于输出排序结果
    	for(i = 1; i <= length_A; i++)
    		B[i] = 0;
    	for(j = length_A; j >= 1; j--)
    	{
    		//如果<=A[j]的数字的个数是x,那么排序后A[j]应该出现在第x个位置，即B[x]=A[j]
    		B[C[A[j]]] = A[j];
    		C[A[j]]--;
    	}
    	delete C;
    }
    //基数排序调用的稳定排序
    void Stable_Sort(int *A, int *B, int k, int d)
    {
    	int i, j;
    	//将C数组初始化为0，用于计数
    	int *C = new int[k+1];
    	for(i = 0; i <= k; i++)
    		C[i] = 0;
    	int *D = new int[length_A+1];
    	for(j = 1; j <= length_A; j++)
    	{
    		//D[j]表示第[j]个元素的第i位数字
    		D[j] = A[j] % (int)pow(10.0, d) / (int)pow(10.0, d-1);
    		//C[j]表示数字D[j]在数组A中出现的次数
    		C[D[j]]++;
    	}
    	//C[i]表示所以<=i的数字出现过的次数
    	for(i = 1; i <= k; i++)
    		C[i] = C[i] + C[i-1];
    	//初始化B为0，B用于输出排序结果
    	for(i = 1; i <= length_A; i++)
    		B[i] = 0;
    	for(j = length_A; j >= 1; j--)
    	{
    		//如果<=D[j]的数字的个数是x,那么排序后A[j]应该出现在第x个位置，即B[x]=A[j]
    		B[C[D[j]]] = A[j];
    		C[D[j]]--;
    	}
    	delete []C;
    	delete []D;
    }
    //基数排序
    void Radix_Sort(int *A, int *B)
    {
    	int i, j;
    	//依次对每一位进行排序，从低位到高位
    	for(i = 1; i <= digit; i++)
    	{
    		Stable_Sort(A, B, 9, i);
    		//输入的是A，输出的是B，再次排序时要把输出数据放入输出数据中
    		for(j = 1; j <= length_A; j++)
    		A[j] = B[j];
    	}
    }
    
    int main()
    {
    	cin>>length_A>>digit;
    	int *A = new int[length_A+1];
    	int *B = new int[length_A+1];
    	int i;
    	//随机产生length_A个digit位的数据
    	for(i = 1; i <= length_A; i++)
    	{
    		A[i] = 0;
    		while(A[i] < (int)pow(10.0, digit-1))
    			A[i] = rand() % (int)pow(10.0, digit);
    	}
    	Print(A, 1, length_A);
    //	Counting_Sort(A, B, 9);
    	Radix_Sort(A, B);
    	Print(A, 1, length_A);
    	delete []A;
    	delete []B;
    	return 0;
    }

# 三、练习 #

## 8.1 排序算法时间的下界 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  8.1-1  
2.  决策树是一棵二叉树，每个节点表示元素之间一组可能的排序，它与已进行的比较相一致，比较的结果是树的边。  
3.  令T是深度为d的二叉树，则T最多有2^T片叶子。具有L片叶子的二叉树深度至少是lgL。  
4.  n个元素排序会有n!个不同的大小关系，其决策树必然有n!片树叶，因此决策树的深度至少是lg(n!)

8.1-1
    决策树是一棵二叉树，每个节点表示元素之间一组可能的排序，它与已进行的比较相一致，比较的结果是树的边。
    令T是深度为d的二叉树，则T最多有2^T片叶子。具有L片叶子的二叉树深度至少是lgL。
    n个元素排序会有n!个不同的大小关系，其决策树必然有n!片树叶，因此决策树的深度至少是lg(n!)

## 8.2 计数排序 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  8.2-1因为假设待排序数据的范围中\[0,k\]，所以B被初始化为-1  
2.      A = \{6 0 2 0 1 3 4 6 1 3 2\}  
3.  ==> C = \{2 2 2 2 1 0 2\}  
4.  ==> C = \{2 4 6 8 9 9 11\}  
5.  ==> B = \{-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1\}  
6.      C = \{2 4 5 8 9 9 11\}  
7.  ==> B = \{-1 -1 -1 -1 -1 2 -1 3 -1 0 -1 -1\}  
8.      C = \{2 4 5 7 9 9 11\}  
9.  ==> B = \{-1 -1 -1 1 -1 2 -1 3 -1 -1 -1\}  
10.     C = \{2 3 5 7 9 9 11\}  
11. ==> B = \{-1 -1 -1 1 -1 2 -1 3 -1 -1 6\}  
12.     C = \{2 3 5 7 9 9 10\}  
13. ==> B = \{-1 -1 -1 1 -1 2 -1 3 4 -1 6\}  
14.     C = \{2 3 5 7 8 9 10\}  
15. ==> B = \{-1 -1 -1 1 -1 2 3 3 4 -1 6\}  
16.     C = \{2 3 5 6 8 9 10\}  
17. ==> B = \{-1 -1 1 1 -1 2 3 3 4 -1 6\}  
18.     C = \{2 2 5 6 8 9 10\}  
19. ==> B = \{-1 0 1 1 -1 2 3 3 4 -1 6\}  
20.          C = \{1 2 5 6 8 9 10\}  
21. ==> B = \{-1 0 1 1 2 2 3 3 4 -1 6\}  
22.          C = \{1 2 4 6 8 9 10\}  
23. ==> B = \{0 0 1 1 2 2 3 3 4 -1 6\}  
24.          C = \{0 2 4 6 8 9 10\}  
25. ==> B = \{0 0 1 1 2 2 3 3 4 6 6\}  
26.          C = \{0 2 4 6 8 9 9\}  
27. 8.2-3  
28. 不稳定  
29. 8.2-4  
30. COUNTING-SORT(A, B, k)中步骤L1-L4求出C，ans(a, b) = C\[b\] - C\[a-1\], C\[-1\]=0

8.2-1因为假设待排序数据的范围中[0,k]，所以B被初始化为-1
        A = {6 0 2 0 1 3 4 6 1 3 2}
    ==> C = {2 2 2 2 1 0 2}
    ==> C = {2 4 6 8 9 9 11}
    ==> B = {-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1}
        C = {2 4 5 8 9 9 11}
    ==> B = {-1 -1 -1 -1 -1 2 -1 3 -1 0 -1 -1}
        C = {2 4 5 7 9 9 11}
    ==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 -1}
        C = {2 3 5 7 9 9 11}
    ==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 6}
        C = {2 3 5 7 9 9 10}
    ==> B = {-1 -1 -1 1 -1 2 -1 3 4 -1 6}
        C = {2 3 5 7 8 9 10}
    ==> B = {-1 -1 -1 1 -1 2 3 3 4 -1 6}
        C = {2 3 5 6 8 9 10}
    ==> B = {-1 -1 1 1 -1 2 3 3 4 -1 6}
        C = {2 2 5 6 8 9 10}
    ==> B = {-1 0 1 1 -1 2 3 3 4 -1 6}
             C = {1 2 5 6 8 9 10}
    ==> B = {-1 0 1 1 2 2 3 3 4 -1 6}
             C = {1 2 4 6 8 9 10}
    ==> B = {0 0 1 1 2 2 3 3 4 -1 6}
             C = {0 2 4 6 8 9 10}
    ==> B = {0 0 1 1 2 2 3 3 4 6 6}
             C = {0 2 4 6 8 9 9}
    8.2-3
    不稳定
    8.2-4
    COUNTING-SORT(A, B, k)中步骤L1-L4求出C，ans(a, b) = C[b] - C[a-1], C[-1]=0

## 8.3 基数排序 ##

8.3-1

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.      A = \{COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX\}  
2.  ==> A = \{SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX\}  
3.  ==> A = \{TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB\}  
4.  ==> A = \{BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB\}

A = {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX}
    ==> A = {SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX}
    ==> A = {TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB}
    ==> A = {BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB}

8.3-2  
稳定排序有：插入排序，合并排序

方法：为每一个元素加入一个最初位置的属性，但两个元素的value一样大时，比较position，这样不会有相同的两个元素

额外空间：O(4n)

8.3-4

把整数转换为n进制再排序，见 [算法导论8.3-4][8.3-4]

8.3-5

最坏情况下需要d遍

## 8.4 桶排序 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  8.4-1  
2.      A = ｛0.79， 0.13， 0.16， 0.64， 0.39， 0.20， 0.89， 0.53， 0.71， 0.42｝  
3.  ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.79， 0.71， 0.89｝  
4.  ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.71， 0.79， 0.89｝  
5.  8.4-2  
6.  最坏情况是O(n^2)  
7.  修改：使用最坏情况下时间为O(nlgn)的算法来处理桶的插入操作  
8.  8.4-3  
9.  E(X^2)=1/4 \* 0 + 1/2 \* 1 + 1/4 \* 4 = 3/2  
10. E^2(X)=\[1/4 \* 0 + 1/2 \* 1 + 1/4 \* 2\]^2 = 1^2 = 1  
11. 8.4-4  
12. 假设分为n个桶  
13. BUCKET-SORT(A)  
14. 1    n <- length\[A\]  
15. 2    for i <- 1 to n  
16. 3    do insert A\[i\] to list B\[n\*(A\[i\].x^2 + A\[i\].y^2)\]  
17. 4    for i <- 0 to n-1  
18. 5        do sort list B\[i\] with insertion sort  
19. 6    concatenate the lists B\[0\], B\[1\], ……,B\[n-1\] together in order  
20. 8.4-5

8.4-1
        A = ｛0.79， 0.13， 0.16， 0.64， 0.39， 0.20， 0.89， 0.53， 0.71， 0.42｝
    ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.79， 0.71， 0.89｝
    ==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.71， 0.79， 0.89｝
    8.4-2
    最坏情况是O(n^2)
    修改：使用最坏情况下时间为O(nlgn)的算法来处理桶的插入操作
    8.4-3
    E(X^2)=1/4 * 0 + 1/2 * 1 + 1/4 * 4 = 3/2
    E^2(X)=[1/4 * 0 + 1/2 * 1 + 1/4 * 2]^2 = 1^2 = 1
    8.4-4
    假设分为n个桶
    BUCKET-SORT(A)
    1    n <- length[A]
    2    for i <- 1 to n
    3    do insert A[i] to list B[n*(A[i].x^2 + A[i].y^2)]
    4    for i <- 0 to n-1
    5        do sort list B[i] with insertion sort
    6    concatenate the lists B[0], B[1], ……,B[n-1] together in order
    8.4-5

# 四、思考题 #

## 8-2 以线性时间原地转换排序 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a)计数排序  
2.  b)快速排序  
3.  c)稳定排序  
4.  d)基数排序要求所使用的排序方法是满足的（条件2），如果要在O(bn)时间内完成，所使用算法的时间应该是O(n)（条件1），所以只有a可以  
5.  e)不稳定  
6.  COUNTING-SORT(A, k)  
7.   1    for i <- 0 to k  
8.   2        do C\[i\] <- 0  
9.   3    for j <-1 to length\[A\]  
10.  4        C\[A\[j\]\] <- C\[A\[j\]\] + 1  
11.  5    cnt <- 1  
12.  6    for i <- 1 to k  
13.  7        while C\[i\] > 0  
14.  8            A\[cnt\] <- i  
15.  9            C\[i\] <- C\[j\] - 1  
16. 10            cnt <- cnt + 1

a)计数排序
    b)快速排序
    c)稳定排序
    d)基数排序要求所使用的排序方法是满足的（条件2），如果要在O(bn)时间内完成，所使用算法的时间应该是O(n)（条件1），所以只有a可以
    e)不稳定
    COUNTING-SORT(A, k)
     1    for i <- 0 to k
     2        do C[i] <- 0
     3    for j <-1 to length[A]
     4        C[A[j]] <- C[A[j]] + 1
     5    cnt <- 1
     6    for i <- 1 to k
     7        while C[i] > 0
     8            A[cnt] <- i
     9            C[i] <- C[j] - 1
    10            cnt <- cnt + 1

## 8-3 排序不同长的数据项 ##

见 [算法导论-8-3-排序不同长度的数据项][-8-3-]

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a)先用计数排序算法法按数字位数排序O(n)，再用基数排序的方法分别对每个桶中的元素排序O(n)  
2.  b)递归使用计数排序，先依据第一个字母进行排序，首字相同的放在同一组，再对每一组分别使用计数排序的方法比较第二个字母  
3.  见到有人用字典树，也是可以的

a)先用计数排序算法法按数字位数排序O(n)，再用基数排序的方法分别对每个桶中的元素排序O(n)
    b)递归使用计数排序，先依据第一个字母进行排序，首字相同的放在同一组，再对每一组分别使用计数排序的方法比较第二个字母
    见到有人用字典树，也是可以的

## 8-4 水壶 ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a)最原始的比较方法，所有的红水壶与所有的蓝水壶依次比较  
2.  c)算法类似于快排，由于不是同种颜色的水壶之间比较，所以采用交叉比较  
3.  step1：从红色水壶中随机选择一个  
4.  step2：以红色水壶为主元对蓝色水壶进行划分  
5.  step3：划分的结果是两个数组，并得到与红色水壶相同大小的蓝色水壶  
6.  step4：以这个蓝色水壶为主元，对红色水壶进行划分  
7.  step5：用step1到step4的过程不断迭代

a)最原始的比较方法，所有的红水壶与所有的蓝水壶依次比较
    c)算法类似于快排，由于不是同种颜色的水壶之间比较，所以采用交叉比较
    step1：从红色水壶中随机选择一个
    step2：以红色水壶为主元对蓝色水壶进行划分
    step3：划分的结果是两个数组，并得到与红色水壶相同大小的蓝色水壶
    step4：以这个蓝色水壶为主元，对红色水壶进行划分
    step5：用step1到step4的过程不断迭代

## 8-5 平均排序 ##

见 [算法导论6.5-8堆排序-K路合并][6.5-8_-K]

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a)1排序是完全排序  
2.  b)1，3，2，4，5，7，6，8，9，10  
3.  d)  
4.  step1：分别把1, 1+k, 1+2k, 1+3k,……;2, 2+k, 2+2k, 2+3k,……；……当作是单独的集合  
5.  step2：对每个集合进行排序时间为O(nlg(n/k))  
6.  e)  
7.  step1：同d)step1  
8.  step2：用堆排序进行k路合并

转载自：[http://blog.csdn.net/mishifangxiangdefeng/article/details/7678859][http_blog.csdn.net_mishifangxiangdefeng_article_details_7678859]

[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7678859#
[8.3-4]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839
[-8-3-]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7686099
[6.5-8_-K]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7668486
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7678859]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7678859