大家好,今天帶來的是自己實現的用C++完成基數排序.在數據結構,算法分析和程序設計的學習過程中,我們經常也無法避免的要學到排序的算法.排序算法是程序設計過程中使用頻率極高的算法之一,其輸入是一組無序的序列,要求以升序或者降序的方式輸出一組有序的序列.對於如二分查找等算法,要求輸入是有序的序列,也就是要先排序後查找,由此可見排序算法的重要性.
廣為人知的排序算法有冒泡排序,還有選擇排序,插入排序.高級一些的有快速排序,希爾排序,堆排序,歸並排序,基數排序等. 其中時間復雜度為O(n*logn)的算法有快速排序,歸並排序和堆排序等,其中快速排序的使用最為廣泛.時間復雜度為O(n2)的算法有冒泡排序,選擇排序和插入排序等.
基數排序是一種非比較的排序算法,它是以桶排序為基礎的.它們在現代計算機出現之前,一直被用於老式穿孔卡的排序.
基數排序的基本思想是:一共有10個"桶",代表各個數位為0~9.在每個桶上,組織一個優先隊列,對於輸入的一系列正整數和0,按照個位的大小關系分別進入10個"桶"中.然後遍歷每個"桶",按照十位的大小關系進行調整,緊接著是百位,千位.......直到到達最大數的最大位數.結合圖例,我們可以理解這個算法:
在C++實現中,我用到了隊列這一數據結構作為每個"桶"的組織方式,因為取數總是從最下方取,而放入數這是放入"桶"的頂部,這與隊列的隊頭出對,隊尾入隊的方式相似.對10個"桶"的組織,則采用向量vector.這個程序支持,輸入序列一定范圍內不限個數,且在int數據類型表示范圍內的非負數排序,根據最大數的位數來決定排序趟數.將數據類型從int改為long或者long long ,則可對更大的整數排序.
排序函數如下:
1 vector<int> radix_sort(vector<int> in)
2 {
3 vector<queue<int>> bucket(10); //十個桶為一個向量,每個桶又是一個隊列
4 int max_value = in.at(0);
5
6 for (auto &i : in)
7 {
8 if ( i > max_value)
9 max_value = i;
10 } //找出輸入的最大元素
11
12 int n = 0;
13
14 for (; max_value != 0; max_value /= 10, ++n)
15 ; //得到最多位數,也即排序趟數
16
17 for (auto &i : in)
18 bucket.at(0).push(i); //全部放入第一個桶
19
20 int i = 0; //趟數控制變量
21 int m = 0; //提取各個位數有關的控制變量
22 int k = 0; //桶數控制變量
23 int x = 0; //桶的大小,因動態改變了容器,迭代器會失效,不使用迭代器
24 int y = 0; //桶內部控制變量
25 int j = 0;
26 int item = 0; //桶內元素
27
28 for (; i < n ; ++i) //趟數循環
29 {
30 for ( k = 0; k < 10 ; ++k) //遍歷每個桶
31 {
32 x = bucket.at(k).size();
33
34 if ( !x )
35 continue;
36
37 for (y = 0; y < x ; ++y) //遍歷桶中隊列的元素
38 {
39 item = j = bucket.at(k).front();
40
41 for (m = i; m > 0; --m) //提取出各個位
42 j /= 10;
43
44 switch (j % 10) //進入相應的桶
45 {
46 case 0:
47 bucket.at(0).push(item);
48 break;
49
50 case 1:
51 bucket.at(1).push(item);
52 break;
53
54 case 2:
55 bucket.at(2).push(item);
56 break;
57
58 case 3:
59 bucket.at(3).push(item);
60 break;
61
62 case 4:
63 bucket.at(4).push(item);
64 break;
65
66 case 5:
67 bucket.at(5).push(item);
68 break;
69
70 case 6:
71 bucket.at(6).push(item);
72 break;
73
74 case 7:
75 bucket.at(7).push(item);
76 break;
77
78 case 8:
79 bucket.at(8).push(item);
80 break;
81
82 case 9:
83 bucket.at(9).push(item);
84 break;
85
86 default: //異常檢測,捕捉與處理
87 try
88 {
89 throw runtime_error("Error!");
90 }
91 catch (runtime_error err)
92 {
93 cout << err.what() << endl;
94 exit(EXIT_FAILURE);
95 }
96 }
97
98 bucket.at(k).pop();
99 }
100 }
101 }
102
103 vector<int> out; //定義一個新的向量,將所有桶的數據收集起來作為最後結果
104
105 for ( i = 0; i < 10; ++i )
106 {
107 int num = bucket.at(i).size();
108
109 for (int ai = 0; ai < num; ++ai)
110 {
111 out.push_back( bucket.at(i).front() );
112 bucket.at(i).pop();
113 }
114 } //排序結果到一個向量中
115
116 return out; //返回這個有序的序列
117
118 }
算法要得到正確結果,要注意的是同一個桶的元素的順序,是從下至上遞增的,這是由遍歷時從代表0的"桶"開始和從桶中取
元素時是從下取保證的.再有,最後從桶中取出元素時也要注意順序.
謝謝大家!轉載請注明出處,謝謝合作!
