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 }