基数排序
基数排序(Radix Sort)是一种非比较型整数排序算法。其基本思想是:将整数按位切割成不同的数字,然后按每个位数分别进行排序(通常用计数排序或桶排序),从低位到高位依次进行,最终得到有序序列。
点击“执行一步”观察算法状态变化。
- 找出待排序序列的最大位数
- 从最低位到最高位,依次对各位进行稳定排序(如计数排序)
- 重复 次后,序列有序
伪代码如下:
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); // 从个位到最高位
}
基数排序与计数排序、桶排序的对比
三者都属于非比较排序,可突破 下界:
| 算法 | 思路 | 时间复杂度 | 空间 |
|---|---|---|---|
| 计数排序 | 统计每个值的个数 | ||
| 桶排序 | 分桶后桶内排序 | ||
| 基数排序 | 逐位计数排序 |
基数排序本质上是多趟计数排序,利用稳定性从低位到高位累积完成整体排序。
- 最好/最坏/平均情况:,为位数,为基数
- 空间复杂度:
- 稳定性:稳定排序
习题 1
对数组 进行基数排序,写出每一位排序后的结果。
解题思路:
本题考查基数排序的逐位排序过程。核心思想是按低位到高位依次做稳定的分配与收集:每一趟按当前位把元素分到对应的桶中并按序收集,从而保证低位优先、高位最终决定次序。
详细步骤:
- 个位排序:[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
基数排序的时间复杂度和空间复杂度分别是多少?
解题思路:
本题考查基数排序的复杂度分析。基数排序的代价由关键字位数和基数共同决定:共做 趟分配,每趟需要 次分配、 次收集并对 个桶初始化,故时间复杂度为 。
详细步骤:
- 时间复杂度 ,其中 为关键字位数、 为基数(每一位的取值个数)。
- 空间复杂度 :用于存放 个桶以及一趟收集所需的输出数组。
- 特点:基数排序不通过关键字的数值大小进行比较,因此其时间是线性的,优于比较类排序的 。
最终答案:
时间 ,空间 。
