核心思想#

• 非比较排序：不比较关键字大小，而是按关键字的每一”位”做分配与收集
• 多关键字排序：将单个关键字拆分为 d 位，每位看作一个子关键字
• 借助稳定的”分配-收集”：对每一位使用桶（队列）完成一趟排序，d 趟后整体有序

算法步骤#

每一趟包含两个步骤：

1. 分配：扫描序列，根据当前位的值将元素放入对应的桶（队列 Q₀~Q_{r-1}）
2. 收集：按桶编号 0→r-1 依次将各桶元素取出，串接成新序列

重复 d 趟（从最低位到最高位），排序完成。

LSD vs MSD#

排序过程示例#

序列 {278, 109, 063, 930, 589, 184, 505, 269, 008, 083}（LSD, d=3, r=10）：

复杂度#

⚠️ 易错：基数排序有 LSD 和 MSD 两种。408 默认考 LSD——从最低位开始排，要求每趟分配使用的排序算法是稳定的。

核心思想#

对每个元素 x，统计比 x 小的元素有多少个，就能直接确定 x 在排序结果中的位置。

算法步骤#

1. 计数：创建计数数组 C[0..k]，统计每个值出现的次数
2. 累加：对 C 做前缀和——C[i] 表示值 ≤ i 的元素总个数
3. 输出：从后往前扫描 A，根据 C 确定每个元素的最终位置

代码实现#

1
void CountingSort(int A[], int B[], int n, int k) {
2
    int C[k + 1];
3
    memset(C, 0, sizeof(C));
4
    for (int i = 0; i < n; i++)     // 计数
5
        C[A[i]]++;
6
    for (int i = 1; i <= k; i++)    // 前缀和
7
        C[i] += C[i - 1];
8
    for (int i = n - 1; i >= 0; i--) {  // 从后往前保证稳定
9
        B[C[A[i]] - 1] = A[i];
10
        C[A[i]]--;
11
    }
12
}

复杂度#

⚠️ 易错：计数排序的稳定性依赖于第 3 步从后往前扫描。如果从前往后，相同值的元素会被反序放置。

⚠️ 易错：计数排序只适合顺序存储，因为需要根据计数值直接定位下标。