#### **序言：当数据有界，排序可以是线性的！**

在学习了快速排序、归并排序等基于比较的O(n log n)算法后，我们可能会产生一个疑问：**排序的效率极限真的就是O(n log n)吗**？

答案是否定的。这个O(n log n)的下限**仅适用于基于元素间比较的排序算法**。如果我们能利用待排序数据本身的特性（例如，它们都是小范围内的整数），就可以设计出更高效的算法。计数排序正是这样一个天才的解决方案。

它的思想极其朴素：**既然要排序，为什么不直接数一数每个数字出现了多少次呢**？ 通过统计频次，我们就能直接确定每个元素在最终有序数组中的位置。这种“不走寻常路”的思路，使其在满足特定条件下，能够达到惊人的**O(n + k)线性时间复杂度**（其中k是数据的范围）。

---

### **第一章：历史与思想起源**

计数排序的概念最早可以追溯到20世纪50年代，作为**基数排序**（Radix Sort）的一个子程序被提出和使用。它并非由某一位科学家单独发明，而是作为一种解决特定问题的实用技巧，在早期处理打孔卡片（punched cards）等具有固定数值范围的数据时自然演化而来。

计数排序的真正价值在于它打破了“所有排序都必须比较”的思维定式。它向我们展示了**信息论**（Information Theory）在算法设计中的力量：如果输入数据携带了额外的、可被利用的信息（如取值范围小），那么我们就可以绕过通用的比较模型，实现超乎想象的效率。

---

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

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

计数排序适用于排序**非负整数**，且这些整数的**最大值`k`不是特别大**的情况。

其核心步骤分为三步：
1.  **计数**（Counting） 创建一个大小为`k+1`的计数数组`count[]`。遍历输入数组，统计每个元素`i`出现的次数，并存入`count[i]`。
2.  **累加**（Accumulating） 对计数数组进行累加操作，使得`count[i]`的值变为**小于等于`i`的元素总个数**。这一步确定了每个元素在输出数组中的**最后一个**位置（为了保证稳定性）。
3.  **输出**（Output） 从后向前遍历输入数组（这是保证稳定性的关键！）。对于每个元素`arr[j]`，根据`count[arr[j]]`找到其在输出数组中的位置，放入该位置，并将`count[arr[j]]`减1。

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

**时间复杂度**：
- **计数阶段**：遍历`n`个元素，O(n)。
- **累加阶段**：遍历`k+1`个计数桶，O(k)。
- **输出阶段**：再次遍历`n`个元素，O(n)。
- **总时间复杂度**：**O(n + k)**。
- 这是一个**线性时间**算法，但前提是`k`与`n`同阶或更小。如果`k`远大于`n`（如对[1, 1000000]排序），则效率会急剧下降。

**空间复杂度**：
- 需要一个大小为`k+1`的计数数组和一个大小为`n`的输出数组。
- 因此，空间复杂度为 **O(n + k)**。

**稳定性**：
- **计数排序是稳定的！**
- **原因**：在输出阶段，我们**从后向前**遍历原始数组。当遇到相等的元素时，后出现的元素会被放在输出数组中靠后的位置，从而保持了它们在原始数组中的相对顺序。

---

### **第三章：数据推演——一步步看清“计数”与“定位”**

以数组 `arr = [4, 2, 2, 8, 3, 3, 1]` 为例。最大值 `k = 8`。

**初始状态**: `arr = [4, 2, 2, 8, 3, 3, 1]`

**第一阶段：计数**
- 创建`count`数组（索引0到8），初始化为0。
- 遍历`arr`，统计频次:
  - `count = [0, 1, 2, 2, 1, 0, 0, 0, 1]`
  - (解释: 0出现0次, 1出现1次, 2出现2次, ..., 8出现1次)

**第二阶段：累加**（计算前缀和）
- `count[0]` 保持不变。
- `count[i] += count[i-1]` for i from 1 to 8.
- 结果: `count = [0, 1, 3, 5, 6, 6, 6, 6, 7]`
- (解释: 小于等于1的有1个, 小于等于2的有3个, ..., 小于等于8的有7个)

**第三阶段：输出**（从后向前遍历`arr`）
- **j=6, arr[6]=1**: `count[1]=1` → output[0] = 1; `count[1]--` → `[0, 0, 3, 5, 6, 6, 6, 6, 7]`
- **j=5, arr[5]=3**: `count[3]=5` → output[4] = 3; `count[3]--` → `[0, 0, 3, 4, 6, 6, 6, 6, 7]`
- **j=4, arr[4]=3**: `count[3]=4` → output[3] = 3; `count[3]--` → `[0, 0, 3, 3, 6, 6, 6, 6, 7]`
- **j=3, arr[3]=8**: `count[8]=7` → output[6] = 8; `count[8]--` → `[0, 0, 3, 3, 6, 6, 6, 6, 6]`
- **j=2, arr[2]=2**: `count[2]=3` → output[2] = 2; `count[2]--` → `[0, 0, 2, 3, 6, 6, 6, 6, 6]`
- **j=1, arr[1]=2**: `count[2]=2` → output[1] = 2; `count[2]--` → `[0, 0, 1, 3, 6, 6, 6, 6, 6]`
- **j=0, arr[0]=4**: `count[4]=6` → output[5] = 4; `count[4]--` → `[0, 0, 1, 3, 5, 6, 6, 6, 6]`

**最终输出数组**: `output = [1, 2, 2, 3, 3, 4, 8]`

---

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

#### **4.1 优点**
1.  **线性时间**：在`k = O(n)`的条件下，时间复杂度为O(n)，远快于任何比较排序。
2.  **稳定排序**：保持相等元素的原始顺序。
3.  **实现简单**：逻辑清晰，代码简洁。

#### **4.2 缺点**
1.  **适用范围极窄**：仅适用于**整数**（或可映射为整数）且**取值范围`k`不能太大**的场景。对于浮点数、字符串等无法直接应用。
2.  **空间开销大**：需要O(k)的额外空间。当`k`非常大时（如`k = 2^32`），内存消耗不可接受。
3.  **不是原地排序**：需要O(n)的额外输出空间。

#### **4.3 可用场景（When to Use）**
- **数据范围已知且较小**：例如，对年龄（0-150）、考试分数（0-100）进行排序。
- **作为基数排序的子程序**：基数排序通过多次调用计数排序来处理多位数，是其最重要的应用。
- **需要稳定线性排序的特定场合**。

#### **4.4 不可使用场景（When NOT to Use）**
- **通用目的排序**：面对未知范围的数据，绝对不要使用。
- **浮点数或字符串排序**。
- **`k >> n` 的情况**：例如，对一个只有10个元素但最大值为1亿的数组排序。

---

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

```java
public class CountingSort {

    /**
     * 计数排序实现
     * @param arr 待排序的非负整数数组
     * @return 排序后的新数组
     * @throws IllegalArgumentException 如果输入包含负数
     */
    public static int[] sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr == null ? null : arr.clone();
        }

        // 1. 找到数组中的最大值
        int max = findMax(arr);
        if (max < 0) {
            throw new IllegalArgumentException("计数排序不支持负数");
        }

        // 2. 创建计数数组
        int[] count = new int[max + 1];
        int n = arr.length;
        int[] output = new int[n];

        // 3. 计数阶段
        for (int num : arr) {
            count[num]++;
        }

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

        // 5. 输出阶段（从后向前遍历以保证稳定性）
        for (int j = n - 1; j >= 0; j--) {
            output[count[arr[j]] - 1] = arr[j];
            count[arr[j]]--;
        }

        return output;
    }

    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 = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original: " + java.util.Arrays.toString(arr));
        int[] sorted = sort(arr);
        System.out.println("Sorted:   " + java.util.Arrays.toString(sorted));
    }
}
```

**代码关键点解析**：
- **错误处理**：明确检查并拒绝负数输入。
- **稳定性保障**：输出循环 `for (int j = n - 1; j >= 0; j--)` 是保证稳定性的核心。
- **前缀和**：累加操作 `count[i] += count[i - 1]` 将频次数组转换为位置索引数组。

---

### **结语**

计数排序是一个典型的“特化”算法。它放弃了通用性，换来了在特定领域内的极致性能。理解计数排序，不仅是掌握一种排序技巧，更是学习如何**根据问题的具体约束来设计最优解**。在2026年的技术面试中，面试官很可能会通过询问“如何在线性时间内对[0, 100]范围内的整数排序？”来考察您对非比较排序的理解。此时，自信地阐述计数排序的原理、复杂度和限制，将是您脱颖而出的关键。

在学习了快速排序、归并排序等基于比较的O(n log n)算法后，我们可能会产生一个疑问：排序的效率极限真的就是O(n log n)吗？

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

本文将对突破比较排序O(n log n)下限的非比较型排序算法——计数排序（Counting Sort）进行一次全面而深入的剖析。我们将探讨其简洁而强大的核心思想，通过严谨的数学公式推演其O(n + k)的线性时间复杂度，并阐明其作为“稳定”排序算法的关键优势。文章包含详尽的数据一步步推演、完整的Java工程级代码示例，并深入探讨其在特定数据范围内的无敌性能以及严格的使用限制，助您彻底掌握这一面试

算法

编程语言

职业发展

计数排序是一种高效的非比较排序算法，适用于小范围整数排序，时间复杂度O(n+k)。通过统计元素频次实现线性排序，保持稳定性但需额外空间。适用于年龄、分数等小范围数据排序，是基数排序的基础。

Java

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

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

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

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

社区新版编辑器体验调研

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

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

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

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