C++ 基数排序的实现实例代码

 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 }