基数排序（Radix Sort）

基数排序是一种非比较型整数排序算法，其核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序。基数排序可以采用最低位优先（LSD）或最高位优先（MSD）两种方式，其中LSD更常用。

基数排序的详细过程

1. 算法原理

   • 基数排序通过多次分配和收集过程实现排序。对于整数，每位数字的范围是0-9，因此通常使用10个桶（队列或链表）来临时存储数据。
   • LSD方式从最低位开始排序，逐步向最高位处理；MSD则相反。LSD保证排序的稳定性，且实现更简单。

2. 具体步骤

   • 步骤1：确定最大数字的位数
     首先遍历数组，找到最大值，并计算其位数（如最大值为789，则位数为3）。这将决定排序的轮数。

     • 示例数组：[170, 45, 75, 90, 2, 802, 24, 66]
     • 最大值：802 → 位数：3

   • 步骤2：按位进行分配和收集（LSD）
     从最低位（个位）开始，到最高位（百位）结束，每一轮按当前位的值将元素分配到0-9号桶中，然后按顺序收集回数组。

     • 第1轮（个位）：
       • 分配：按个位数字放入桶中
         • 桶0: 170, 90
         • 桶2: 2, 802
         • 桶4: 24
         • 桶5: 45, 75
         • 桶6: 66
         • 其他桶为空
       • 收集：按桶号0-9顺序取出 → [170, 90, 2, 802, 24, 45, 75, 66]
     • 第2轮（十位）：
       • 分配：按十位数字放入桶中（注意：2的十位为0）
         • 桶0: 2, 802
         • 桶2: 24
         • 桶4: 45
         • 桶6: 66
         • 桶7: 170, 75
         • 桶9: 90
       • 收集：→ [2, 802, 24, 45, 66, 170, 75, 90]
     • 第3轮（百位）：
       • 分配：按百位数字放入桶中（不足百位补0）
         • 桶0: 2, 24, 45, 66, 75, 90
         • 桶1: 170
         • 桶8: 802
       • 收集：→ [2, 24, 45, 66, 75, 90, 170, 802]（已排序）

3. 算法分析

   • 时间复杂度：O(d·(n + k))，其中d为最大位数，n为元素个数，k为基数（通常k=10）。当d为常数时，复杂度为线性O(n)。
   • 空间复杂度：O(n + k)，需要额外桶空间。
   • 稳定性：稳定（LSD方式保证相同键值顺序不变）。

4. 适用场景

   • 适用于整数或字符串排序，且位数范围不大。
   • 若最大值位数d很大，效率可能低于比较排序（如快速排序）。

通过多轮按位排序，基数排序避免了直接比较元素，从而在线性时间内完成排序，但依赖数据的位表示和稳定性。