基数排序

定义与基本思想

基数排序（Radix Sort）是一种非比较型整数排序算法。其基本思想是：将整数按位切割成不同的数字，然后按每个位数分别进行排序（通常用计数排序或桶排序），从低位到高位依次进行，最终得到有序序列。

基数排序演示

17045759080224266

当前处理位：个位

算法描述

找出待排序序列的最大位数 $d$
从最低位到最高位，依次对各位进行稳定排序（如计数排序）
重复 $d$ 次后，序列有序

伪代码如下：

function radixSort(A, d):
    for i = 1 to d:
        对A按第i位进行稳定排序（如计数排序）

代码实现

// 按第 exp 位（个位 exp=1，十位 exp=10...）进行计数排序
void CountSortByDigit(int A[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(A[i] / exp) % 10]++;   // 统计该位的数字分布
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];     // 累加
    for (int i = n - 1; i >= 0; i--) {
        int digit = (A[i] / exp) % 10;
        output[count[digit] - 1] = A[i];  // 稳定放置
        count[digit]--;
    }
    for (int i = 0; i < n; i++) A[i] = output[i];
}

void RadixSort(int A[], int n) {
    int max = A[0];
    for (int i = 1; i < n; i++)
        if (A[i] > max) max = A[i];
    for (int exp = 1; max / exp > 0; exp *= 10)
        CountSortByDigit(A, n, exp);  // 从个位到最高位
}

基数排序与计数排序、桶排序的对比

三者都属于非比较排序，可突破 $O(n\log n)$ 下界：

算法	思路	时间复杂度	空间
计数排序	统计每个值的个数	$O(n+k)$	$O(k)$
桶排序	分桶后桶内排序	$O(n+k)$	$O(n+k)$
基数排序	逐位计数排序	$O(d(n+r))$	$O(n+r)$

基数排序本质上是多趟计数排序，利用稳定性从低位到高位累积完成整体排序。

时间复杂度分析

最好/最坏/平均情况： $O(d(n+r))$ ， $d$ 为位数， $r$ 为基数
空间复杂度： $O(n+r)$
稳定性：稳定排序

习题

习题 1

对数组 $A = [170, 45, 75, 90, 802, 24, 2, 66]$ 进行基数排序，写出每一位排序后的结果。

答案与解析

解题思路：按个位、十位、百位依次排序。

详细步骤：

个位排序：[170, 90, 802, 2, 24, 45, 75, 66]
十位排序：[802, 2, 24, 45, 66, 170, 75, 90]
百位排序：[2, 24, 45, 66, 75, 90, 170, 802]

答案：如上，最终有序。

习题 2

基数排序的时间复杂度和空间复杂度分别是多少？

答案与解析

解题思路：考查复杂度和空间。

详细步骤：

时间复杂度 $O(d(n+r))$
空间复杂度 $O(n+r)$

答案：时间 $O(d(n+r))$ ，空间 $O(n+r)$ 。

上一章节归并排序介绍归并排序的基本思想、算法流程、复杂度分析及典型习题。

下一章节教学大纲本大纲详细列出了数据结构课程的考查目标和考试范围。