颠覆你的排序认知！基数排序（Radix Sort）详细教程

伯灵

发布于 2026-01-21 09:36:44

2240

1. 引言

在算法世界里，排序无疑是最基础但也最重要的操作之一。你可能已经熟悉了快速排序、归并排序等经典算法，但今天要介绍的是 基数排序（Radix Sort），一种能在特定场景下 击败 O(n log n) 排序算法 的强大武器！

本文将深入剖析基数排序的核心原理，详细解析其实现过程，并通过 Java 代码示例让你彻底掌握这一高效的排序算法。

2. 基数排序的原理

基数排序是一种 非比较 排序算法，依赖于“分桶”思想进行排序。它的核心思想是 按照数位（位权）进行多轮排序，从最低位到最高位依次进行，最终得到有序结果。

2.1 基数排序的工作流程

以 LSD（最低位优先） 方法为例：

按个位数分桶，按顺序取出；
按十位数分桶，按顺序取出；
按百位数分桶，按顺序取出；
依此类推，直到处理最高位。

2.2 适用场景

基数排序 适用于数据范围固定 且 位数不多 的情况，例如：

整数排序（如电话号码、学号排序）
字符串排序（如字典排序）

在这些场景下，基数排序可以达到 O(n) 线性时间复杂度，比 O(n log n) 的快速排序还要高效！

3. Java 实现基数排序

下面是基数排序的 Java 实现：

import java.util.*;

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt(); // 找到最大值，确定位数
        int exp = 1;
        while (max / exp > 0) {
            countingSortByDigit(arr, exp);
            exp *= 10;
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // 统计当前位数的频率
        for (int num : arr) {
            count[(num / exp) % 10]++;
        }

        // 计算累积和，确定元素存放位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 按当前位的顺序填充到 output 数组
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // 拷贝回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

代码解析

radixSort: 依次按照个位、十位、百位……进行排序。
countingSortByDigit: 采用 计数排序 对某一数位进行稳定排序。
main: 测试基数排序的效果。

运行结果：

排序前: [170, 45, 75, 90, 802, 24, 2, 66]
排序后: [2, 24, 45, 66, 75, 90, 170, 802]

4. 基数排序 vs 其他排序算法

排序算法	时间复杂度	适用场景
快速排序	O(n log n)	适用于一般场景
归并排序	O(n log n)	需要稳定排序时
计数排序	O(n + k)	适用于范围小的整数
基数排序	O(d * (n + k))	适用于固定位数的整数

优势：

适用于大规模整数排序
线性时间复杂度，在某些情况下比 O(n log n) 更快
稳定排序，保留相同值的4. 基数排序 vs 其他排序算法排序算法时间复杂度适用场景快速排序O(n log n)适用于一般场景归并排序O(n log n)需要稳定排序时计数排序O(n + k)适用于范围小的整数基数排序O(d * (n + k))适用于固定位数的整数优势：
- 适用于大规模整数排序
- 线性时间复杂度，在某些情况下比 O(n log n) 更快
- 稳定排序，保留相同值的相对顺序

劣势：