算法导论8.3-4 O(n)时间内对[0..n^-1]之间的n个数排序 .

待我称王封你为后i 2022-05-14 03:27 170阅读 0赞

# 一、题目 #

如何在O(n)时间内，对0到n^2-1之间的n个整数进行排序

# 二、思路 #

把整数转换为n进制再排序，每个数有两位，每位的取值范围是\[0..n-1\]，再进行基数排序

# 三、代码 #

**\[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 n, radix, length\_A, digit = 2;  
6.  void Print(int \*A, int start, int end)  
7.  \{  
8.      int i;  
9.      for(i = start; i <= end; i++)  
10.     \{  
11.         if(i == start)cout<<'\{';  
12.         else cout<<' ';  
13.         cout<<A\[i\];  
14.     \}  
15.     cout<<'\}'<<endl;  
16. \}  
17. //基数排序调用的稳定排序   
18. void Stable\_Sort(int \*A, int \*B, int k, int d)  
19. \{  
20.     int i, j;  
21.     //将C数组初始化为0，用于计数   
22.     int \*C = new int\[k+1\];  
23.     for(i = 0; i <= k; i++)  
24.         C\[i\] = 0;  
25.     int \*D = new int\[length\_A+1\];  
26.     for(j = 1; j <= length\_A; j++)  
27.     \{  
28.         //D\[j\]表示第\[j\]个元素的第i位数字   
29.         D\[j\] = A\[j\] % (int)pow(radix\*1.0, d) / (int)pow(radix\*1.0, d-1);  
30.         //C\[j\]表示数字D\[j\]在数组A中出现的次数   
31.         C\[D\[j\]\]++;  
32.     \}  
33.     //C\[i\]表示所以<=i的数字出现过的次数    
34.     for(i = 1; i <= k; i++)  
35.         C\[i\] = C\[i\] + C\[i-1\];  
36.     //初始化B为0，B用于输出排序结果   
37.     for(i = 1; i <= length\_A; i++)  
38.         B\[i\] = 0;  
39.     for(j = length\_A; j >= 1; j--)  
40.     \{  
41.         //如果<=D\[j\]的数字的个数是x,那么排序后A\[j\]应该出现在第x个位置，即B\[x\]=A\[j\]   
42.         B\[C\[D\[j\]\]\] = A\[j\];  
43.         C\[D\[j\]\]--;  
44.     \}  
45.     delete \[\]C;  
46.     delete \[\]D;  
47. \}  
48. //基数排序   
49. void Radix\_Sort(int \*A, int \*B)  
50. \{  
51.     int i, j;  
52.     //依次对每一位进行排序，从低位到高位   
53.     for(i = 1; i <= digit; i++)  
54.     \{  
55.         Stable\_Sort(A, B, radix-1, i);  
56.         //输入的是A，输出的是B，再次排序时要把输出数据放入输出数据中    
57.         for(j = 1; j <= length\_A; j++)  
58.             A\[j\] = B\[j\];  
59.     \}  
60. \}  
61.   
62. int main()  
63. \{  
64.     cin>>n;  
65.     length\_A = n;  
66.     int \*A = new int\[n+1\];  
67.     int \*B = new int\[n+1\];  
68.     bool flag\[1000\]  = \{0\};  
69.     int i;  
70.     //生产n个随机的数据范围在0到n^-1之间   
71.     for(i = 1; i <= n; i++)  
72.     \{  
73.         do  
74.         \{  
75.             A\[i\] = rand() % (n\*n);  
76.         \}while(flag\[A\[i\]\]);  
77.         flag\[A\[i\]\] = 1;  
78.     \}  
79.     Print(A, 1, n);  
80.     radix = n;  
81.     Radix\_Sort(A, B);  
82.     Print(A, 1, n);  
83.     return 0;  
84. \}

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

[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839#
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7685839]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7685839