基数排序

概述

基数排序（Radix Sort） 是一种非比较排序算法，按元素的各位（从最低有效位到最高有效位，或反之）依次使用稳定排序（通常是 计数排序）进行排序，时间复杂度为 $\Theta (d(n+k))$，其中 $d$ 为位数，$k$ 为基数。

定义

基数排序

基数排序对 $n$ 个 $d$ 位数（每个位是 $0$ 到 $k-1$ 之间的值）进行排序。

算法步骤（LSD 版本，从最低有效位开始）：

1. 从最低有效位（个位）到最高有效位，依次对每一位使用稳定的排序算法（如计数排序）。
2. 经过 $d$ 趟处理后，数组即被排序。

时间复杂度：$\Theta (d(n+k))$ 空间复杂度：$\Theta (n+k)$

核心性质

为什么必须使用稳定排序？

基数排序的关键在于：在对第 $i$ 位排序时，不能破坏前 $i-1$ 位已经排好的相对顺序。只有使用稳定排序才能保证这一点。

LSD vs MSD

• LSD（Least Significant Digit）：从最低位开始排序，实现简单，通常使用计数排序作为子程序。
• MSD（Most Significant Digit）：从最高位开始排序，需要递归处理，适用于变长关键字。

时间复杂度分析

• 当 $d$ 为常数且 $k=O(n)$ 时，基数排序的运行时间为 $\Theta (n)$。
• 选择计数排序作为子程序时，每趟耗时 $\Theta (n+k)$，共 $d$ 趟。

与比较排序的关系

基数排序不受比较排序 $\Omega (n\lg n)$ 下界的限制，可以在特定条件下实现线性时间排序。

章节扩展

第8章：线性时间排序

基数排序是第8章讨论的三种非比较排序算法之一，与计数排序和桶排序共同展示了突破比较排序下界的方法。

参见

• 计数排序
• 比较排序
• 稳定排序