[代碼實例]基數排序的C++實現

　　大家好,今天帶來的是自己實現的用C++完成基數排序.在數據結構,演算法分析和程式設計的學習過程中,我們經常也無法避免的要學到排序的演算法.排序演算法是程式設計過程中使用頻率極高的演算法之一,其輸入是一組無序的序列,要求以升序或者降序的方式輸出一組有序的序列.對於如二分查找等演算法,要求輸入是有序的序列,也就是要先排序後查找,由此可見排序演算法的重要性.

　　廣為人知的排序演算法有冒泡排序,還有選擇排序,插入排序.高級一些的有快速排序,希爾排序,堆排序,歸併排序,基數排序等. 其中時間複雜度為O(n*logn)的演算法有快速排序,歸併排序和堆排序等,其中快速排序的使用最為廣泛.時間複雜度為O(n²)的演算法有冒泡排序,選擇排序和插入排序等.

　　基數排序是一種非比較的排序演算法,它是以桶排序為基礎的.它們在現代電腦出現之前,一直被用於老式穿孔卡的排序.

　　基數排序的基本思想是:一共有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的"桶"開始和從桶中取
     元素時是從下取保證的.再有,最後從桶中取出元素時也要註意順序.

謝謝大家!轉載請註明出處,謝謝合作!