C++ 基數(shù)排序
大家好,今天帶來的是自己實現(xiàn)的用C++完成基數(shù)排序.在數(shù)據(jù)結(jié)構(gòu),算法分析和程序設計的學習過程中,我們經(jīng)常也無法避免的要學到排序的算法.排序算法是程序設計過程中使用頻率極高的算法之一,其輸入是一組無序的序列,要求以升序或者降序的方式輸出一組有序的序列.對于如二分查找等算法,要求輸入是有序的序列,也就是要先排序后查找,由此可見排序算法的重要性.
廣為人知的排序算法有冒泡排序,還有選擇排序,插入排序.高級一些的有快速排序,希爾排序,堆排序,歸并排序,基數(shù)排序等. 其中時間復雜度為O(n*logn)的算法有快速排序,歸并排序和堆排序等,其中快速排序的使用最為廣泛.時間復雜度為O(n2)的算法有冒泡排序,選擇排序和插入排序等.
基數(shù)排序是一種非比較的排序算法,它是以桶排序為基礎(chǔ)的.它們在現(xiàn)代計算機出現(xiàn)之前,一直被用于老式穿孔卡的排序.
基數(shù)排序的基本思想是:一共有10個"桶",代表各個數(shù)位為0~9.在每個桶上,組織一個優(yōu)先隊列,對于輸入的一系列正整數(shù)和0,按照個位的大小關(guān)系分別進入10個"桶"中.然后遍歷每個"桶",按照十位的大小關(guān)系進行調(diào)整,緊接著是百位,千位.......直到到達最大數(shù)的最大位數(shù).結(jié)合圖例,我們可以理解這個算法:
在C++實現(xiàn)中,我用到了隊列這一數(shù)據(jù)結(jié)構(gòu)作為每個"桶"的組織方式,因為取數(shù)總是從最下方取,而放入數(shù)這是放入"桶"的頂部,這與隊列的隊頭出對,隊尾入隊的方式相似.對10個"桶"的組織,則采用向量vector.這個程序支持,輸入序列一定范圍內(nèi)不限個數(shù),且在int數(shù)據(jù)類型表示范圍內(nèi)的非負數(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ù)有關(guān)的控制變量 22 int k = 0; //桶數(shù)控制變量 23 int x = 0; //桶的大小,因動態(tài)改變了容器,迭代器會失效,不使用迭代器 24 int y = 0; //桶內(nèi)部控制變量 25 int j = 0; 26 int item = 0; //桶內(nèi)元素 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ù)收集起來作為最后結(jié)果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 } //排序結(jié)果到一個向量中115 116 return out; //返回這個有序的序列117 118 }算法要得到正確結(jié)果,要注意的是同一個桶的元素的順序,是從下至上遞增的,這是由遍歷時從代表0的"桶"開始和從桶中取 元素時是從下取保證的.再有,最后從桶中取出元素時也要注意順序.
新聞熱點
疑難解答
