C++ 基數(shù)排序的實現(xiàn)實例代碼
C++ 基數(shù)排序
大家好,今天帶來的是自己實現(xiàn)的用C++完成基數(shù)排序.在數(shù)據(jù)結構,算法分析和程序設計的學習過程中,我們經(jīng)常也無法避免的要學到排序的算法.排序算法是程序設計過程中使用頻率極高的算法之一,其輸入是一組無序的序列,要求以升序或者降序的方式輸出一組有序的序列.對于如二分查找等算法,要求輸入是有序的序列,也就是要先排序后查找,由此可見排序算法的重要性.
廣為人知的排序算法有冒泡排序,還有選擇排序,插入排序.高級一些的有快速排序,希爾排序,堆排序,歸并排序,基數(shù)排序等. 其中時間復雜度為O(n*logn)的算法有快速排序,歸并排序和堆排序等,其中快速排序的使用最為廣泛.時間復雜度為O(n2)的算法有冒泡排序,選擇排序和插入排序等.
基數(shù)排序是一種非比較的排序算法,它是以桶排序為基礎的.它們在現(xiàn)代計算機出現(xiàn)之前,一直被用于老式穿孔卡的排序.
基數(shù)排序的基本思想是:一共有10個"桶",代表各個數(shù)位為0~9.在每個桶上,組織一個優(yōu)先隊列,對于輸入的一系列正整數(shù)和0,按照個位的大小關系分別進入10個"桶"中.然后遍歷每個"桶",按照十位的大小關系進行調整,緊接著是百位,千位.......直到到達最大數(shù)的最大位數(shù).結合圖例,我們可以理解這個算法:
在C++實現(xiàn)中,我用到了隊列這一數(shù)據(jù)結構作為每個"桶"的組織方式,因為取數(shù)總是從最下方取,而放入數(shù)這是放入"桶"的頂部,這與隊列的隊頭出對,隊尾入隊的方式相似.對10個"桶"的組織,則采用向量vector.這個程序支持,輸入序列一定范圍內不限個數(shù),且在int數(shù)據(jù)類型表示范圍內的非負數(shù)排序,根據(jù)最大數(shù)的位數(shù)來決定排序趟數(shù).將數(shù)據(jù)類型從int改為long或者long long ,則可對更大的整數(shù)排序.
排序函數(shù)如下:
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 ; //得到最多位數(shù),也即排序趟數(shù)
16
17 for (auto &i : in)
18 bucket.at(0).push(i); //全部放入第一個桶
19
20 int i = 0; //趟數(shù)控制變量
21 int m = 0; //提取各個位數(shù)有關的控制變量
22 int k = 0; //桶數(shù)控制變量
23 int x = 0; //桶的大小,因動態(tài)改變了容器,迭代器會失效,不使用迭代器
24 int y = 0; //桶內部控制變量
25 int j = 0;
26 int item = 0; //桶內元素
27
28 for (; i < n ; ++i) //趟數(shù)循環(huán)
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; //定義一個新的向量,將所有桶的數(shù)據(jù)收集起來作為最后結果
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的"桶"開始和從桶中取 元素時是從下取保證的.再有,最后從桶中取出元素時也要注意順序.
相關文章
這篇文章主要介紹了C++ assert()函數(shù)用法案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
這篇文章主要為大家介紹了Visual?Studio中的解決方案中不顯示項目問題分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
這篇文章主要為大家詳細介紹了C++課程設計之學生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
本文主要介紹了C++17之std::any的具體使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
C++靜態(tài)成員函數(shù)不能調用非靜態(tài)成員變量(詳解)
下面小編就為大家?guī)硪黄狢++靜態(tài)成員函數(shù)不能調用非靜態(tài)成員變量(詳解)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要為大家詳細介紹了OpenCV外接USB攝像頭的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
VSCode插件開發(fā)全攻略之package.json詳解
這篇文章主要介紹了VSCode插件開發(fā)全攻略之package.json的相關知識，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05
今天小編就為大家分享一篇減少OpenCV讀取高分辨率圖像的時間示例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
本章將會詳細講解二叉樹遍歷的四種方式，分別為前序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷。在學習遍歷之前，會先帶大家回顧一下二叉樹的基本概念2022-02-02
C語言全方位講解指針與地址和數(shù)組函數(shù)堆空間的關系
指針是C語言中一個非常重要的概念，也是C語言的特色之一。使用指針可以對復雜數(shù)據(jù)進行處理，能對計算機的內存分配進行控制，在函數(shù)調用中使用指針還可以返回多個值2022-04-04