C++ 基數排序的完成實例代碼。本站提示廣大學習愛好者：（C++ 基數排序的完成實例代碼）文章只能為提供參考，不一定能成為您想要的結果。以下是C++ 基數排序的完成實例代碼正文
C++ 基數排序
大家好,明天帶來的是自己完成的用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的"桶"開端和從桶中取 元素時是從下取保證的.再有,最後從桶中取出元素時也要留意順序.
