基数排序

定义与基本思想

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

基数排序

点击“执行一步”观察算法状态变化。

算法描述

  1. 找出待排序序列的最大位数 dd
  2. 从最低位到最高位,依次对各位进行稳定排序(如计数排序)
  3. 重复 dd 次后,序列有序

伪代码如下:

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(nlog⁡n)O(n\log n) 下界:

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

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

时间复杂度分析

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

习题

习题 1

对数组 A=[170,45,75,90,802,24,2,66]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]
  4. 说明:每一趟分配与收集都保持上一趟的相对次序(稳定),最高位排完后整个序列即为有序序列。

最终答案:

如上,最终有序。

习题 2

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

基数排序时间复杂度空间复杂度基数与位数

解题思路:

本题考查基数排序的复杂度分析。基数排序的代价由关键字位数和基数共同决定:共做 dd 趟分配,每趟需要 nn 次分配、nn 次收集并对 rr 个桶初始化,故时间复杂度为 O(d(n+r))O(d(n+r))。

详细步骤:

  1. 时间复杂度 O(d(n+r))O(d(n+r)),其中 dd 为关键字位数、rr 为基数(每一位的取值个数)。
  2. 空间复杂度 O(n+r)O(n+r):用于存放 rr 个桶以及一趟收集所需的输出数组。
  3. 特点:基数排序不通过关键字的数值大小进行比较,因此其时间是线性的,优于比较类排序的 O(nlog⁡n)O(n \log n)。

最终答案:

时间 O(d(n+r))O(d(n+r)),空间 O(n+r)O(n+r)。

发现内容有问题?

告诉我们哪里需要改进。