【数据结构与算法-Day 45】超越比较的极限：详解非比较排序之王——基数排序

大模型铲屎官

989人浏览 · 2026-01-01 22:01:06

大模型铲屎官 · 2026-01-01 22:01:06 发布

Langchain系列文章目录

01-玩转LangChain：从模型调用到Prompt模板与输出解析的完整指南
 02-玩转 LangChain Memory 模块：四种记忆类型详解及应用场景全覆盖
 03-全面掌握 LangChain：从核心链条构建到动态任务分配的实战指南
 04-玩转 LangChain：从文档加载到高效问答系统构建的全程实战
 05-玩转 LangChain：深度评估问答系统的三种高效方法（示例生成、手动评估与LLM辅助评估）
06-从 0 到 1 掌握 LangChain Agents：自定义工具 + LLM 打造智能工作流！
07-【深度解析】从GPT-1到GPT-4：ChatGPT背后的核心原理全揭秘
 08-【万字长文】MCP深度解析：打通AI与世界的“USB-C”，模型上下文协议原理、实践与未来

数据结构与算法系列文章目录

文章目录

Langchain系列文章目录
Python系列文章目录
PyTorch系列文章目录
机器学习系列文章目录
深度学习系列文章目录
Java系列文章目录
JavaScript系列文章目录
Python系列文章目录
Go语言系列文章目录
Docker系列文章目录
数据结构与算法系列文章目录
摘要
一、温故知新：为什么需要非比较排序？
- 1.1 比较排序的性能瓶颈
- 1.2 非比较排序的核心思想
二、基数排序 (Radix Sort) 核心原理剖析
- 2.1 生活中的类比：图书馆图书卡片排序
- 2.2 基数排序的基本流程
- 2.3 关键：稳定的子排序算法
- 2.4 图解 LSD 基数排序
三、基数排序的实现 (Java)
- 3.1 准备工作：获取最大值
- 3.2 核心实现：LSD 基数排序
- 3.3 MSD 基数排序简介
四、性能分析与应用场景
- 4.1 时间复杂度分析
- 4.2 空间复杂度分析
- 4.3 稳定性分析
- 4.4 适用场景与局限性
- - - （1）适用场景
    - （2）局限性
五、各大排序算法总结与对比
六、总结

摘要

在上一篇文章中，我们探讨了计数排序和桶排序这两种非比较排序算法，它们通过“空间换时间”的策略，在特定条件下突破了比较排序 $\log n)$ 的性能下限。本文将继续深入非比较排序的领域，介绍一位重量级成员——基数排序 (Radix Sort)。基数排序是一种非常巧妙的整数排序算法，其核心思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。它不直接比较整个数字的大小，而是通过多轮“分配”与“收集”的过程，最终实现整个序列的有序。本文将从基数排序的直观理解、核心原理、代码实现、性能分析到应用场景，对其进行全面而深入的剖析，并最终提供一份各大排序算法的综合对比表，助你构建完整的排序知识体系。

一、温故知新：为什么需要非比较排序？

在正式学习基数排序之前，我们有必要回顾一下排序算法的两大阵营，以更好地理解基数排序的定位与价值。

1.1 比较排序的性能瓶颈

我们已经学习过的大多数排序算法，如冒泡排序、快速排序、归并排序、堆排序等，都属于比较排序。它们的核心逻辑依赖于元素之间的直接比较（>、<、=）来确定它们的相对顺序。

一个重要的结论是：任何基于比较的排序算法，其最优（最坏情况）时间复杂度不可能低于 $\log n)$ 。这可以通过决策树模型来证明，一个包含 n 个元素的决策树，其叶子节点至少有 $n!$ 个，树的高度至少为 $log_2(n!)$ ，根据斯特林公式近似，这个高度就是 $\log n)$ 。这意味着，无论我们如何优化，只要算法的根基是“比较”，就无法超越这个理论下限。

1.2 非比较排序的核心思想

为了打破 $\log n)$ 的壁垒，非比较排序应运而生。它们另辟蹊径，不依赖元素间的比较，而是利用待排序元素的自身特性（如数值范围、构成等）来排序。

计数排序 (Counting Sort)：适用于整数范围不大的场景，通过统计每个整数出现的次数来排序。
桶排序 (Bucket Sort)：将数据分布到有限数量的桶里，对每个桶再分别排序。

这些算法能达到线性时间复杂度 $O (n)$ ，但通常有较强的限制条件。基数排序正是这个家族中应用广泛且思想独特的一员。

二、基数排序 (Radix Sort) 核心原理剖析

基数排序的核心思想是“多关键字排序”，它将一个复杂的关键字（如一个多位数）分解为多个简单的、有优先级的关键字（如个位、十位、百位），然后依次对这些简单关键字进行排序。

2.1 生活中的类比：图书馆图书卡片排序

想象一下，你是一名图书管理员，需要整理一大叠借书卡，每张卡上都有一个 3 位的图书编号（例如，从 000 到 999）。你该如何快速排序？

一种直观但低效的方法是：直接比较两个卡片的 3 位数大小。
一种更聪明、更机械化的方法是：

第一轮 (按个位数)：准备 10 个盒子（编号 0-9）。遍历所有卡片，根据卡片编号的个位数，将它们放入对应的盒子。例如，编号 173 放入 3 号盒，251 放入 1 号盒。放完后，按 0-9 的顺序从盒子里依次取出所有卡片，形成一个新的序列。
第二轮 (按十位数)：对新序列重复上述过程，但这次依据的是十位数。例如，251 放入 5 号盒，173 放入 7 号盒。完成后，再次按顺序取出所有卡片。
第三轮 (按百位数)：同理，依据百位数进行第三轮的分配与收集。

当三轮结束后，你会惊奇地发现，所有的卡片已经完全按编号从小到大排好序了！这个过程就是基数排序最常见的 LSD (Least Significant Digit first) 模式。

2.2 基数排序的基本流程

基数排序的执行过程可以概括为以下几个步骤：

2.2.1 确定最大位数

首先，需要遍历整个待排序数组，找到最大值，并计算出它的位数（d）。这个位数决定了我们需要进行多少轮的“分配-收集”过程。

2.2.2 从最低位到最高位 (LSD)

我们从最低有效位（个位）开始，一直处理到最高有效位。每一轮都针对当前位进行排序。

2.2.3 每一轮的“分配”与“收集”

这是基数排序的核心循环。

分配 (Distribution)：遍历数组中的每个元素，根据当前处理位上的数字（0-9），将其放入相应的“桶”中。
收集 (Collection)：将所有桶中的元素按照桶的编号（0 到 9）顺序依次收集起来，形成新一轮的数组，用于下一轮的分配。

2.3 关键：稳定的子排序算法

在上面的图书卡片例子中，有一个隐藏的关键点：当我们将卡片放入盒子，再取出来时，必须保持它们在放入前已有的相对顺序。

例如，在按十位数排序时，我们有 024 和 814 两个数。在上一轮（按个位）排序后，它们的顺序可能就是 [..., 814, ..., 024, ...]。当按十位数分配时，814 进入 1 号桶，024 进入 2 号桶。如果我们的“桶”内排序是不稳定的，可能会导致它们的相对顺序颠倒。

因此，基数排序每一轮所依赖的排序算法必须是稳定的。计数排序天生就是稳定的，并且非常适合对 0-9 范围内的数字进行排序，因此它成为实现基数排序内部排序的最佳选择。

2.4 图解 LSD 基数排序

让我们通过一个具体的例子 [170, 45, 75, 90, 802, 24, 2, 66] 来直观感受一下 LSD 基数排序的过程。最大数是 802，有 3 位，所以需要 3 轮排序。

三、基数排序的实现 (Java)

下面我们将用 Java 代码完整实现 LSD 基数排序。

3.1 准备工作：获取最大值

我们需要一个辅助方法来找到数组中的最大值，从而确定排序的轮数。

// 获取数组中的最大值
private static int getMaxValue(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

3.2 核心实现：LSD 基数排序

我们将每一轮的“分配-收集”过程封装在一个 countingSortForRadix 方法中，该方法实际上就是一个针对特定位的计数排序。

import java.util.Arrays;

public class RadixSort {

    /**
     * 基数排序主函数
     * @param arr 待排序数组
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 1. 找到数组中的最大值，以确定最大位数
        int maxValue = getMaxValue(arr);

        // 2. 从个位开始，对数组进行每一位的排序
        // exp 代表当前处理的位（1, 10, 100, ...）
        for (int exp = 1; maxValue / exp > 0; exp *= 10) {
            countingSortForRadix(arr, exp);
        }
    }

    /**
     * 针对基数排序的特定位进行计数排序（稳定的）
     * @param arr 待排序数组
     * @param exp 当前处理的位（例如，1表示个位，10表示十位）
     */
    private static void countingSortForRadix(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 临时输出数组，存储本轮排序结果
        int[] count = new int[10]; // 计数数组，用于存放 0-9 各个数字的个数

        // 3. 统计每个桶（0-9）中的元素个数
        for (int i = 0; i < n; i++) {
            // 计算当前位上的数字
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // 4. 将 count[i] 转换为该数字在 output[] 中的结束位置
        // 这一步是保证排序稳定性的关键
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 5. 反向遍历原数组，将元素放入 output 数组的正确位置
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            // count[digit] - 1 就是该元素在本轮排序后的位置
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 6. 将排序好的 output 数组复制回原数组 arr
        System.arraycopy(output, 0, arr, 0, n);
    }

    // 获取数组中的最大值
    private static int getMaxValue(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    // 测试
    public static void main(String[] args) {
        int[] data = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original array: " + Arrays.toString(data));
        radixSort(data);
        System.out.println("Sorted array:   " + Arrays.toString(data));
    }
}

3.3 MSD 基数排序简介

除了从最低位开始的 LSD (Least Significant Digit)，还有一种从最高位开始的 MSD (Most Significant Digit) 基数排序。

工作方式：MSD 首先按最高位进行分配，将数据分到不同的桶中。然后，对每个桶中的数据递归地进行 MSD 排序（处理次高位），直到所有数据排序完毕。
优缺点：
- 优点：在某些情况下，当高位就能区分大部分数据时，可能提前完成排序，效率更高。
- 缺点：实现上通常使用递归，空间开销大，且实现复杂。对于数据分布不均的情况，可能会导致某些桶内元素过多，递归深度不平衡。

由于 LSD 实现简单、空间效率稳定且对缓存友好，因此在实际应用中比 MSD 更为常见。

四、性能分析与应用场景

4.1 时间复杂度分析

基数排序的性能由两个因素决定：排序的轮数 d 和每一轮排序的时间 T(n)。

d：待排序数组中最大值的位数。对于一个最大值为 M 的数，其十进制位数为 $\lfloor \log_{10}M \rfloor + 1$ 。
T(n)：每一轮我们使用计数排序，其时间复杂度为 $O (n + k)$ ，其中 n 是数组元素个数，k 是基数（对于十进制数，k=10）。

因此，基数排序的总时间复杂度为： $\cdot (n+k))$
当 k（基数）固定时（如10），复杂度简化为 $\cdot n)$ 。如果所有数字的位数 d 也是一个常数或者远小于 n，那么基数排序的时间复杂度可以近似看作线性时间 $O (n)$ 。

4.2 空间复杂度分析

基数排序需要额外的空间来存储计数数组和临时输出数组。

计数数组 count 的大小为 k。
临时输出数组 output 的大小为 n。

所以，空间复杂度为 $O (n + k)$ 。

4.3 稳定性分析

基数排序是稳定的。它的稳定性完全依赖于其内部使用的子排序算法的稳定性。我们实现的 countingSortForRadix 正是通过巧妙地计算累积频次并反向填充来保证稳定性的。

4.4 适用场景与局限性

（1）适用场景

整数排序：特别是当整数的范围很大，但位数相对较少时，基数排序非常高效。
字符串排序：可以按字符对字符串进行基数排序。
特定格式数据排序：如日期（年、月、日）、IP地址等，这些都可以看作是多关键字数据。

（2）局限性

数据类型限制：基数排序要求数据能够被拆分为独立的“位”，并且位与位之间有明确的优先级。这使得它不适用于浮点数或复杂对象的直接排序（除非能映射为整数）。
空间消耗：需要 $O (n + k)$ 的额外空间，当 n 很大时，这是一个不小的开销。
对长短不一的数据不友好：例如对单词排序，如果单词长度差异很大，处理起来会比较麻烦（通常需要补齐或特殊处理）。

五、各大排序算法总结与对比

至此，我们已经学习了所有主流的排序算法。下表对它们进行一个全面的总结和对比，以便你在实际工作中做出最佳选择。

算法 (Algorithm)	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性	备注
冒泡排序 (Bubble)	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	稳定	实现简单，但效率低下，基本只用于教学。
选择排序 (Selection)	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	不稳定	不受数据初始顺序影响，交换次数少。
插入排序 (Insertion)	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	稳定	对于近乎有序的数组效率极高。
希尔排序 (Shell)	$O(n^{1.3})$	$O (n)$	$O(n^2)$	$O (1)$	不稳定	插入排序的改进版，性能优于 $O(n^2)$ 排序。
归并排序 (Merge)	$\log n)$	$\log n)$	$\log n)$	$O (n)$	稳定	性能稳定，常用于外部排序。
快速排序 (Quick)	$\log n)$	$\log n)$	$O(n^2)$	$O(\log n)$	不稳定	综合性能最好，是应用最广泛的排序算法。
堆排序 (Heap)	$\log n)$	$\log n)$	$\log n)$	$O (1)$	不稳定	空间复杂度为 $O (1)$ 的 $\log n)$ 排序。
计数排序 (Counting)	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (n + k)$	稳定	非比较排序，`k`为整数范围，适用于`k`较小的场景。
桶排序 (Bucket)	$O (n + k)$	$O (n + k)$	$O(n^2)$	$O (n + k)$	稳定	非比较排序，适用于数据均匀分布的场景。
基数排序 (Radix)	$O (d (n + k))$	$O (d (n + k))$	$O (d (n + k))$	$O (n + k)$	稳定	非比较排序，`d`为位数，`k`为基数。适用于整数排序。

六、总结

本文深入探讨了非比较排序算法中的基数排序，为我们的排序算法系列画上了一个圆满的句号。

核心思想：基数排序是一种非比较排序算法，它避免了元素间的直接比较，而是通过“多关键字排序”的思想，将待排元素（如整数）拆分成多个独立的“位”（如个、十、百位），然后从低位到高位（或反之）依次进行排序。
工作机制：最常见的LSD基数排序，通过多轮的“分配-收集”循环完成排序。每一轮都依赖一个稳定的子排序算法（通常是计数排序）来处理当前位，从而保证前几轮的排序成果得以保留。
性能特点：基数排序的时间复杂度为 $O (d (n + k))$ ，在位数d和基数k可控的情况下，其性能可达线性级别，优于任何比较排序。其空间复杂度为 $O (n + k)$ 。
选择之道：通过最后的排序算法大比拼表格，我们可以清晰地看到，没有“最好”的算法，只有“最合适”的算法。在面对具体问题时，应充分考虑数据规模、数据特性（范围、分布）、对稳定性的要求以及内存限制，从而选择最优的排序策略。

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能