基数排序

定义与基本思想

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

基数排序演示

17045759080224266

当前处理位：个位

下一步

算法描述

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

伪代码如下：

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

时间复杂度分析

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

练习题

练习 1

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

参考答案

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

详细步骤：

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

答案：如上，最终有序。

练习 2

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

参考答案

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

详细步骤：

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

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