#### **序言：用“分治”思想驯服数字的每一位**

在计数排序和桶排序之后，我们已经见识了利用数据范围特性实现线性时间排序的可能性。但它们都有一个共同的局限：要么要求数据范围小（计数排序），要么要求数据分布均匀（桶排序）。

**基数排序则提供了一条全新的路径**。 它的天才之处在于，它不试图一次性对整个数字进行排序，而是**将一个复杂的排序问题分解为多个简单的子问题**。具体来说，它按位（个位、十位、百位...）来处理数字。通过从最低有效位（LSD）或最高有效位（MSD）开始，依次对每一位进行稳定的排序，最终神奇地得到一个完全有序的序列。

这种“大事化小”的策略，使得基数排序能够处理非常大的数值范围，只要位数`d`是可控的。它是早期计算机（打孔卡制表机）时代的产物，却因其优雅和高效，在今天的大数据和高性能计算领域依然焕发着生机。

---

### **第一章：历史溯源——打孔卡与人口普查的革命**

基数排序的故事始于19世纪末的美国。1880年的人口普查耗时近8年才完成，面对即将爆炸性增长的人口，美国人口普查局急需一种更高效的统计方法。

**赫尔曼·何乐礼**（Herman Hollerith），一位年轻的统计工程师，受火车票检票员在车票上打孔记录信息的启发，发明了**打孔卡片制表机**（Tabulation Machine）。他的系统使用打孔卡来存储每个人的信息（如年龄、性别、职业），每个特征对应卡片上的特定列。

为了对这些卡片进行分类和计数，何乐礼设计了一种机械分拣方法：机器会根据某一列（比如代表年龄的十位数）是否有孔，将卡片分拣到不同的盒子（桶）中。然后，操作员会按顺序收集这些盒子中的卡片，并对下一列（个位数）重复此过程。经过几轮这样的分拣，所有卡片就按年龄排好了序。

这一发明不仅将1890年的人口普查时间缩短到了不到一年，还直接催生了后来的IBM公司。何乐礼的机械分拣过程，正是现代**LSD**（Least Significant Digit first）的物理原型。

---

### **第二章：核心思想与数学推演**

#### **2.1 算法原理**

基数排序有两种主要方法：
- **LSD**（Least Significant Digit first） 从最低位（个位）开始排序，逐位向高位推进。**必须使用稳定的排序算法作为子程序**（通常是计数排序）。这是最常用的方法，适用于固定长度的键。
- **MSD**（Most Significant Digit first） 从最高位开始排序，递归地对每个桶进行排序。这种方法更像传统的快速排序，但实现更复杂。

本文重点介绍**LSD基数排序**，其步骤如下：
1.  **确定最大位数**：找到数组中的最大值，确定需要处理的总位数`d`。
2.  **逐位排序**：从个位（exp=1）开始，到最高位（exp=10^(d-1)）结束，对每一位执行以下操作：
    a. 使用**计数排序**（或其他稳定排序）对当前位进行排序。

#### **2.2 数学推导：复杂度分析**

假设：
- `n`：待排序元素的数量。
- `d`：最大元素的位数。
- `k`：每一位可能的取值范围（对于十进制，k=10；对于二进制，k=2）。

**时间复杂度**：
- 对每一位进行计数排序的时间复杂度为O(n + k)。
- 总共需要处理`d`位。
- **总时间复杂度**：**O(d * (n + k))**。
- 当`d`和`k`相对于`n`是常数时（例如，对32位整数排序，d=10, k=10），时间复杂度为 **O(n)**，即线性时间。

**空间复杂度**：
- 计数排序需要O(k)的计数数组和O(n)的输出数组。
- 因此，空间复杂度为 **O(n + k)**。

**稳定性**：
- **基数排序（LSD）是稳定的！**
- **原因**：其正确性完全依赖于子排序算法（计数排序）的稳定性。因为是从低位向高位排序，高位的排序结果会覆盖低位的结果。只有当高位相同时，低位的相对顺序才有意义，而稳定的子排序保证了这一点。

---

### **第三章：数据推演——一步步看清“按位”排序的魔力**

以数组 `arr = [170, 45, 75, 90, 2, 802, 24, 66]` 为例。

**初始状态**: `[170, 45, 75, 90, 2, 802, 24, 66]`
- 最大值是802，共3位（d=3）。

**第一轮：按个位**（exp=1）
- 提取个位: `[0, 5, 5, 0, 2, 2, 4, 6]`
- 使用计数排序后，数组变为: `[170, 90, 2, 802, 24, 45, 75, 66]`
  - (解释: 个位为0的`170,90`在前；个位为2的`2,802`次之；...)

**第二轮：按十位**（exp=10）
- 提取十位: `[7, 9, 0, 0, 2, 4, 7, 6]`
- 使用计数排序后，数组变为: `[2, 802, 24, 45, 66, 170, 75, 90]`
  - (解释: 十位为0的`2,802`在前；十位为2的`24`次之；十位为4的`45`；...)

**第三轮：按百位**（exp=100）
- 提取百位: `[1, 8, 0, 0, 0, 1, 0, 0]`
- 使用计数排序后，数组变为: `[2, 24, 45, 66, 75, 90, 170, 802]`
  - (解释: 百位为0的`2,24,45,66,75,90`在前；百位为1的`170`；百位为8的`802`)

**最终结果**: `[2, 24, 45, 66, 75, 90, 170, 802]` —— 完美有序！

---

### **第四章：优缺点与应用场景深度剖析**

#### **4.1 优点**
1.  **线性时间性能**：在`d`和`k`为常数时，时间复杂度为O(n)，快于任何比较排序。
2.  **稳定排序**：保持相等元素的原始顺序。
3.  **可扩展性强**：不仅可以排序整数，还可以排序字符串、日期等任何可以表示为固定长度键的数据。

#### **4.2 缺点**
1.  **适用范围有限**：需要能够将元素分解为独立的“位”或“字符”。对于浮点数，需要特殊处理。
2.  **空间开销**：需要O(n + k)的额外空间。
3.  **常数因子**：虽然渐近复杂度优秀，但内部循环（多次调用计数排序）的常数因子可能较大。

#### **4.3 可用场景（When to Use）**
- **对大量整数进行排序**，尤其是位数不多时（如IP地址、电话号码）。
- **作为其他算法的子程序**。
- **需要稳定且快速的排序，且数据格式符合要求**。

#### **4.4 不可使用场景（When NOT to Use）**
- **通用目的排序**：面对任意对象或无法分解的数据。
- **内存极度受限的环境**。

---

### **第五章：Java工程实践**

```java
public class RadixSort {

    /**
     * 基数排序（LSD）主入口，适用于非负整数
     * @param arr 待排序的整型数组
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 1. 找到最大值以确定位数
        int max = findMax(arr);

        // 2. 从个位开始，对每一位进行计数排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    /**
     * 根据指定的位（exp）对数组进行计数排序
     * @param arr 数组
     * @param exp 位数（1代表个位，10代表十位，100代表百位...）
     */
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 十进制，所以是0-9，共10个桶

        // 1. 计数
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // 2. 累加（计算前缀和）
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 3. 构建输出数组（从后向前以保证稳定性）
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 4. 将output复制回原数组
        System.arraycopy(output, 0, arr, 0, n);
    }

    private static int findMax(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[] arr = {170, 45, 75, 90, 2, 802, 24, 66};
        System.out.println("Original: " + java.util.Arrays.toString(arr));
        sort(arr);
        System.out.println("Sorted:   " + java.util.Arrays.toString(arr));
    }
}
```

**代码关键点解析**：
- **`exp`变量**：巧妙地用于提取每一位数字 `(arr[i] / exp) % 10`。
- **内嵌计数排序**：`countingSortByDigit` 方法是计数排序的定制版，只关注当前位。
- **稳定性保障**：在构建输出数组时，同样采用从后向前遍历的策略。

---

### **结语**

基数排序是算法史上的一座丰碑，它完美地诠释了“分而治之”的哲学。从何乐礼的打孔卡到今天的Java代码，其核心思想历经百年而不衰。它告诉我们，面对复杂问题，有时最好的策略不是正面强攻，而是将其拆解为一系列简单、可管理的子任务。在2026年的技术面试中，能够清晰阐述基数排序的历史、原理、复杂度以及与计数排序的关系，并手写出无Bug的代码，将充分证明您不仅掌握了知识，更理解了智慧。

在计数排序和桶排序之后，我们已经见识了利用数据范围特性实现线性时间排序的可能性。但它们都有一个共同的局限：要么要求数据范围小（计数排序），要么要求数据分布均匀（桶排序）。

【数据结构面试】 基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

本文将对一种能够突破O(n log n)比较排序下限的非比较型排序算法——基数排序（Radix Sort）进行一次全面而深入的剖析。我们将追溯其由**赫尔曼·何乐礼**（Herman Hollerith）在1887年为处理美国人口普查数据而发明的辉煌历史，通过严谨的数学公式推演其O(d*(n + k))的时间复杂度，并阐明其作为“稳定”排序算法的核心优势。文章包含详尽的数据一步步推演、完整的Jav

编程语言

职业发展

算法

基数排序是一种高效的非比较排序算法，通过按位分解数字实现线性时间复杂度。它从最低位开始逐位排序，利用计数排序作为子程序，适用于大范围整数排序。算法时间复杂度O(d*(n+k))，空间复杂度O(n+k)，具有稳定性。广泛应用于IP地址、电话号码等固定长度数据的排序场景。

大数据

Java

2026采购季 | AI焕新·智启新局

thpc

bigdata-class

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

【数据结构面试】 基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析-腾讯云开发者社区-腾讯云

【数据结构面试】基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

【数据结构面试】基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【数据结构面试】 基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

【数据结构面试】 基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【数据结构面试】基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析

【数据结构面试】基数排序（Radix Sort）Java实现（2026最新）：时间复杂度、空间复杂度与稳定性全解析