1.4.1 基数排序的原理

基数排序算法的核心思想是：利用除法和取余即可得到一个数值的某一位。基数排序算法，即根据数值的位（如个位、十位、百位等）来进行排序的算法，该算法有点类似哈希表。在基数排序中，首先在待排序数中找到最大的数，其次算出该数有几位，最后依次根据个位、十位、百位、千位、…、最大位进行排序。假设对8个数进行基数排序，如表1.1所示。在待排序的数中，最大的数为999，该数有个位、十位和百位。

表1.1 待排序的8个数

（1）根据个位排序，将以上8个数按照个位大小放入对应的桶中，如表1.2所示。

表1.2 按个位排序后，将数据放入相应的桶中

（2）按照从左到右、从上到下的顺序将表1.2桶中的元素重新放入数组arr中，如表1.3所示。

表1.3 个位排序后数组arr中数据元素的重新排列

（3）根据十位进行排序，将以上8个数按照十位大小依次放入对应的桶中，如表1.4所示。

表1.4 按十位排序后，将数据放入相应的桶中

（4）按照从左到右、从上到下的顺序将表1.4桶中的元素重新放入数组arr中，如表1.5所示。

表1.5 十位排序后数组arr中数据元素的重新排列

（5）根据百位进行排序，将以上8个数按照百位大小依次放入对应的桶中，如表1.6所示。

表1.6 按百位排序后，将数据放入相应的桶中

（6）按照从左到右、从上到下的顺序将表1.6桶中的元素重新放入数组arr中，如表1.7所示。

表1.7 百位排序后数组arr中数据元素的重新排列

由上述过程可知，基数排序就是重复进行“置入”与“取出”过程，其整体“置入”与“取出”的次数只与待排序数据的最大值有关。为什么先对“个位”进行排序，而不是我们通常比较两个数时先比较最高位?因为最后排序的位数对结果的影响最大。在此算法中，先排最低位，后排最高位，最低位对最终结果影响最小、最高位对最终结果影响最大，符合客观逻辑。