## 基数排序 1. 基本思想：先比较最低位，也就是个位，进行分桶，分桶过程中分到一个桶中的数据直接追加到桶中即可，无需排序。然后将所有同种的元素按桶的顺序拿出，重新组成序列，然后比较十位，进行分桶…直到比较到最高位，重新组成序列即可完成排序。 2. 基本步骤： * 假设有欲排数据序列如下所示：73  22  93  43  55  14  28  65  39  81 * 首先根据个位数的数值，在遍历数据时将它们各自分配到编号0至9的桶（个位数值与桶号一一对应）中。  * 分配结束后。接下来将所有桶中所盛数据按照桶号由小到大（桶中由顶至底）依次重新收集串起来，得到如下仍然无序的数据序列： 81 22 73 93 43 14 55 65 28 39 * 接着，再进行一次分配，这次根据十位数值来分配（原理同上），分配结果（逻辑想象）如下图所示：  * 分配结束后。接下来再将所有桶中所盛的数据（原理同上）依次重新收集串接起来，得到如下的数据序列： 14 22 28 39 43 55 65 73 81 93。排序完毕，如果排序的数据序列有三位数以上的数据，则重复进行以上的动作直至最高位数为止。 ``` // 求最长位数，个十百对应为1,2,3 int maxDigit(vector<int>& data) { int max = data[0]; for (auto x : data) { if (x > max) max = x; } int digit = 1; while (max / 10 != 0) { max /= 10; digit++; } return digit; } void RadixSort(vector<int>& data) { static int radix = 10; int digit = maxDigit(data); for (int i = 0; i < digit; ++i) { vector<vector<int>> bucket(radix); // 对应0, 1, 2, ... 9十个桶 for (auto x : data) { int r = x % (int)pow(10, i + 1) / (int)pow(10, i); // 求基数对应哪个桶的索引 bucket[r].push_back(x); } int index = 0; for (int r = 0; r < radix; ++r) { for (auto x : bucket[r]) { data[index++] = x; } } } } ```