【数据结构与算法-Day 44】线性时间排序的奥秘：一文搞懂计数排序与桶排序

大模型铲屎官

722人浏览 · 2026-01-01 21:56:01

大模型铲屎官 · 2026-01-01 21:56:01 发布

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 另辟蹊径：非比较排序的核心思想
二、计数排序 (Counting Sort)：以空间换时间的典范
- 2.1 核心思想：数字本身就是最好的索引
- - 2.1.1 算法前提
- 2.2 实现步骤详解
- 2.3 代码实战
- 2.4 性能与特性分析
- 2.5 应用场景与局限性
三、桶排序 (Bucket Sort)：分而治之的升级
- 3.1 核心思想：分桶、排序、合并
- 3.2 实现步骤与可视化
- - 3.2.1 流程拆解
  - 3.2.2 Mermaid 图解流程
- 3.3 代码实战
- 3.4 性能与特性分析
- 3.5 应用场景与关键点
四、终极对决：计数排序 vs. 桶排序
- 4.1 全方位对比表格
- 4.2 如何选择？
五、总结

摘要

在排序算法的江湖中，快速排序、归并排序等基于比较的算法以其 $\log n)$ 的时间复杂度称霸一方。然而，这个复杂度也如同一个难以逾越的“天花板”。本文将带你探索一个全新的领域——非比较排序，并聚焦于其中的两大核心成员：计数排序 (Counting Sort) 和桶排序 (Bucket Sort)。我们将深入剖析它们如何巧妙地利用数据自身的特性，绕开元素间的两两比较，从而在特定场景下实现惊人的 $O (n)$ 线性时间复杂度。通过原理讲解、步骤拆解、代码实战与场景分析，你将彻底掌握这两种高效的排序技术，并理解它们在性能优化中的独特价值。

一、告别比较：为何需要非比较排序？

在我们之前的文章中，无论是冒泡、选择、插入，还是更高效的归并、快速排序，它们的核心逻辑都离不开一件事：比较元素的大小来决定其位置。

1.1 比较排序的“天花板”

经过严格的数学证明，任何基于元素比较的排序算法，其最优的平均时间复杂度都无法低于 $\log n)$ 。这被称为“比较排序的理论下界”。你可以将其想象成一个物理定律，无论你的算法设计得多巧妙，只要你的根基是“比较”，就无法突破这个速度极限。

那么，我们是否就此满足了呢？不。在某些特定条件下，我们可以完全抛弃“比较”这一操作，另辟蹊径，实现更快的排序。

1.2 另辟蹊径：非比较排序的核心思想

非比较排序，顾名思义，它不通过比较元素间的键值来排序。相反，它利用待排序数据的固有特征（例如，数值的范围、分布规律等）来直接确定每个元素的位置。

这类算法通常是线性时间复杂度的，如 $O (n)$ 或 $O (n + k)$ （其中 $k$ 是数据的范围），因此也被称为线性时间排序 (Linear Time Sorting)。

它们之所以能突破 $\log n)$ 的限制，关键在于它们对数据做了某种“假设”。今天，我们就来揭秘其中最经典、最常用的两种算法：计数排序和桶排序。

二、计数排序 (Counting Sort)：以空间换时间的典范

计数排序是一种非常高效但适用场景受限的排序算法。它的核心思想极度简洁，堪称“以空间换时间”的绝佳范例。

2.1 核心思想：数字本身就是最好的索引

想象一下这个场景：统计一个班级所有同学的期末考试成绩（0-100分）并排序。你会怎么做？

一个非常直观的方法是：创建一个有101个“格子”的数组 counts，编号从0到100。然后遍历每个同学的成绩，如果一个同学考了95分，就在 counts[95] 这个格子里加一。遍历完所有同学后，counts 数组就记录了每个分数有多少人。最后，你只需从0到100遍历 counts 数组，counts[i] 是几，就输出几个 i，排序就完成了！

这就是计数排序的精髓：利用待排序的数值本身作为新数组的索引，来统计该数值出现的次数。

2.1.1 算法前提

从上面的例子可以看出，计数排序并非万能，它依赖于一个重要的前提：
待排序的数据必须是整数，且范围不能过大。
如果我们要排序的数据是员工的月薪，范围可能是3000到50000，那么计数数组的长度就会非常大，造成巨大的空间浪费。

2.2 实现步骤详解

为了让计数排序更通用（能处理负数）且稳定（相同元素的相对顺序在排序后不变，这对基数排序等高级算法至关重要），我们采用一个优化版的实现流程。

假设我们有数组 arr = [2, 5, 3, 0, 2, 3, 0, 3]。

（1）确定数据范围

首先，找到数组中的最大值 max = 5 和最小值 min = 0。数据范围大小为 k = max - min + 1 = 6。

（2）创建计数数组

创建一个大小为 k 的计数数组 count，索引从 0 到 5。count 数组的每个索引对应一个原始值。
count 数组初始化为 [0, 0, 0, 0, 0, 0]。

（3）统计元素频率

遍历原数组 arr，将每个元素出现的次数记录在 count 数组中。
例如，遇到第一个 2，则 count[2] 加一；遇到第一个 5，则 count[5] 加一。
遍历结束后，count 数组为 [2, 0, 2, 3, 0, 1]。
（含义：0出现了2次，1出现了0次，2出现了2次…）

（4）累加计数（关键步骤）

这一步是实现稳定性的关键。将 count 数组变换为累加数组。从第二个元素开始，每个元素都等于它自身加上前一个元素的值。
count[i] = count[i] + count[i-1]。
变换过程：

count[1] = count[1] + count[0] = 0 + 2 = 2
count[2] = count[2] + count[1] = 2 + 2 = 4
count[3] = count[3] + count[2] = 3 + 4 = 7
count[4] = count[4] + count[3] = 0 + 7 = 7
count[5] = count[5] + count[4] = 1 + 7 = 8

最终 count 数组为 [2, 2, 4, 7, 7, 8]。
这个新数组的含义是：小于等于索引 i 的元素，在排序后数组中的最终位置是 count[i] - 1。
例如，count[3] = 7 意味着小于等于3的元素一共有7个，所以最后一个3应该放在索引为 7-1=6 的位置。

（5）反向填充结果数组

创建一个与原数组等大的结果数组 result。从后向前遍历原数组 arr，根据 count 数组找到每个元素的正确位置。

遍历到 arr 最后一个元素 3：
- 在 count 数组中查找 3 对应的值：count[3] = 7。
- 这意味着 3 应该放在 result 数组的第 7 个位置，即索引 6。所以 result[6] = 3。
- 将 count[3] 的值减一，变为 6。下次再遇到 3 时，它将被放在索引 5 的位置。
遍历到 arr 倒数第二个元素 0：
- count[0] = 2。
- 放入 result 数组索引 1 的位置：result[1] = 0。
- count[0] 减一，变为 1。
… 以此类推，直到遍历完 arr。

反向遍历的目的是保证稳定性。因为我们从后向前取元素，并根据 count 值从后向前放置，这样就能保证原始数组中靠后的相同元素，在结果数组中也靠后。

（6）结果拷贝

将 result 数组的内容拷贝回原数组 arr。

2.3 代码实战

import java.util.Arrays;

public class CountingSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 1. 找到最大值和最小值，确定范围
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int range = max - min + 1;

        // 2. 创建计数数组
        int[] count = new int[range];

        // 3. 统计元素频率
        for (int num : arr) {
            // 关键：通过偏移量min，将原始值映射到count数组的索引
            count[num - min]++;
        }

        // 4. 累加计数，得到每个元素排序后的最终位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 5. 创建结果数组，反向遍历原数组以保证稳定性
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            // 找到num在count数组中的索引
            int countIndex = num - min;
            // 根据累加计数值，计算num在result数组中的位置（-1是因为数组索引从0开始）
            int resultIndex = count[countIndex] - 1;
            result[resultIndex] = num;
            // 更新count值，为下一个相同元素准备位置
            count[countIndex]--;
        }

        // 6. 将结果拷贝回原数组
        System.arraycopy(result, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 0, 2, 3, 0, 3};
        System.out.println("Original array: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr)); // Output: [0, 0, 2, 2, 3, 3, 3, 5]
    }
}

2.4 性能与特性分析

2.4.1 时间复杂度

$O (n + k)$
- 遍历原数组找最大最小值： $O (n)$ 。
- 遍历原数组统计频率： $O (n)$ 。
- 遍历计数数组累加： $O (k)$ 。
- 遍历原数组填充结果： $O (n)$ 。
- 总计： $O (3 n + k) = O (n + k)$ 。其中 $n$ 是待排序元素个数， $k$ 是数据范围 (max - min + 1)。
当 $k$ 的大小与 $n$ 相当或更小时（例如 $k = O (n)$ ），时间复杂度就是 $O (n)$ ，非常高效。

2.4.2 空间复杂度

$O (k)$
- 主要开销来自计数数组 count，其大小为 $k$ 。此外还有一个 $O (n)$ 的 result 数组，但在某些实现中可以优化。通常我们关注的是与数据范围相关的额外空间，即 $O (k)$ 。

2.4.3 稳定性

稳定
- 我们采用的累加计数和反向填充方案，确保了相同元素的相对顺序不变。

2.5 应用场景与局限性

适用场景：对一定范围内的整数进行排序，如年龄、考试分数、投票统计等。
局限性：
1. 数据范围敏感：当 $k$ 远大于 $n$ 时（例如，排序100个范围在0到1亿之间的数），会造成巨大的空间浪费和时间开销，性能甚至不如 $\log n)$ 算法。
2. 数据类型受限：只能处理整数，无法直接用于小数或字符串排序。

三、桶排序 (Bucket Sort)：分而治之的升级

如果说计数排序是为每个可能的整数值都准备了一个“专属”小格子，那么桶排序则显得更为“大度”和灵活。它为一定范围内的数准备一个“公共”的桶。

3.1 核心思想：分桶、排序、合并

桶排序的工作流程如下：

设置桶 (Buckets)：根据待排序数据的范围和分布，创建若干个有序的桶。
分发 (Scatter)：遍历原始数据，将每个元素根据一个映射函数放入对应的桶中。
桶内排序 (Sort)：对每个非空的桶内的元素进行单独排序。这里可以使用任何排序算法，如插入排序（因为桶内元素通常较少，插入排序很高效）。
收集 (Gather)：按顺序访问每个桶，将桶内已排序的元素依次取出，放回原数组，完成排序。

3.2 实现步骤与可视化

假设我们有数组 arr = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]。

3.2.1 流程拆解

创建桶：假设我们创建10个桶，编号0-9。每个桶可以是一个链表或动态数组。
映射函数：设计一个函数将元素映射到桶。对于 $[0, 1)$ 范围内的浮点数，一个简单的映射函数是 bucket_index = floor(n * element)，其中 n 是桶的数量。
分发元素：
- 0.78 -> floor(10 * 0.78) = 7 -> 放入第7个桶。
- 0.17 -> floor(10 * 0.17) = 1 -> 放入第1个桶。
- …
- 遍历结束后，元素分布如下：
  - 桶0: []
  - 桶1: [0.17, 0.12]
  - 桶2: [0.26, 0.21, 0.23]
  - 桶3: [0.39]
  - …
  - 桶6: [0.68]
  - 桶7: [0.78, 0.72]
  - 桶9: [0.94]
桶内排序：对每个非空桶进行排序。
- 桶1: [0.12, 0.17]
- 桶2: [0.21, 0.23, 0.26]
- …
- 桶7: [0.72, 0.78]
合并结果：按顺序从桶0到桶9，将排好序的元素依次取出，得到最终排序结果：[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]。

3.2.2 Mermaid 图解流程

3.3 代码实战

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BucketSort {

    public static void sort(double[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;
        // 1. 创建桶，桶的数量通常等于元素数量
        List<Double>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new LinkedList<>(); // 使用链表，插入效率高
        }

        // 2. 将元素分发到对应的桶中
        for (double value : arr) {
            // 假设数据在 [0, 1) 范围内
            // 映射函数：int(n * value)
            int bucketIndex = (int) (n * value);
            buckets[bucketIndex].add(value);
        }

        // 3. 对每个桶进行内部排序
        for (int i = 0; i < n; i++) {
            if (!buckets[i].isEmpty()) {
                // 对于桶内元素，可以使用任何排序算法，这里用Java自带的排序
                Collections.sort(buckets[i]);
            }
        }

        // 4. 将所有桶中的元素按顺序合并回原数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (double value : buckets[i]) {
                arr[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        double[] arr = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
        System.out.println("Original array: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

3.4 性能与特性分析

3.4.1 时间复杂度

平均情况： $O (n + k)$
- 假设数据是均匀分布的，那么每个桶里大约有 $n / k$ 个元素（ $k$ 为桶的数量）。如果桶内排序使用插入排序（平均复杂度为 $O(m^2)$ ，m为桶内元素数），总时间是 $\times O((n/k)^2) = O(n + n^2/k)$ 。如果我们选择桶的数量 $\approx n$ ，则复杂度为 $O (n)$ 。
最坏情况： $O(n^2)$
- 如果所有元素都落入同一个桶中，桶排序退化为桶内排序算法的复杂度。如果桶内使用插入排序，则最坏为 $O(n^2)$ 。

3.4.2 空间复杂度

$O (n + k)$
- 需要 $k$ 个桶的指针空间，以及 $n$ 个元素存储在所有桶中的总空间。

3.4.3 稳定性

可以实现为稳定排序
- 取决于桶内排序算法是否稳定。如果桶内使用稳定的排序算法（如插入排序或归并排序），并且将元素放入桶和从桶中收集时都保持顺序，则桶排序是稳定的。

3.5 应用场景与关键点

适用场景：
1. 数据量大。
2. 数据分布相对均匀。
3. 可以处理浮点数。
关键点：
1. 桶的数量：桶的数量是影响性能的关键。太少会导致每个桶元素过多，增加桶内排序时间；太多会造成空间浪费。
2. 映射函数：映射函数必须设计得当，能将数据均匀地分配到各个桶中。

四、终极对决：计数排序 vs. 桶排序

4.1 全方位对比表格

特性	计数排序 (Counting Sort)	桶排序 (Bucket Sort)
核心思想	值->索引，统计频率	范围->桶，分治排序
数据类型	整数	整数、浮点数均可
数据要求	数据范围 $k$ 不能过大	数据分布应相对均匀
时间复杂度	$O (n + k)$ (稳定)	平均 $O (n + k)$ ，最坏 $O(n^2)$
空间复杂度	$O (k)$	$O (n + k)$
稳定性	稳定	取决于桶内排序算法，可实现为稳定
关联关系	桶排序是计数排序的推广，当桶大小为1时，桶排序即为计数排序。	计数排序是桶排序的特例，当每个桶只存放一个值的元素时。

4.2 如何选择？

当待排序的是整数，且最大值和最小值的差 k 不比元素总数 n 大太多时，选择计数排序。 它是最快、最简单的选择。
当数据是浮点数，或者数据范围很大但分布均匀时，选择桶排序。 桶排序更具普适性，但其性能依赖于数据的均匀性。

五、总结

今天我们深入探讨了两种强大的非比较排序算法，它们为我们打开了突破 $\log n)$ 性能瓶颈的大门。

非比较排序的本质：这类算法通过利用数据的内在属性（如数值范围或分布），而不是元素间的比较，来确定元素的顺序，从而在特定条件下实现线性时间复杂度。
计数排序：是一种以空间换时间的策略，它利用整数值作为索引来统计频率。其优点是速度极快 ( $O (n + k)$ )，且是稳定的；缺点是严重依赖数据范围 $k$ ，只适用于整数且范围不能过大的场景。
桶排序：是计数排序思想的泛化和升级。它将数据划分到不同的“桶”中，对每个桶进行独立排序，然后合并。桶排序适用于数据分布均匀的场景，能处理浮点数，但其性能高度依赖于数据的分布情况，最坏情况下可能退化。
选择的智慧：没有最好的算法，只有最合适的算法。理解每种排序算法的原理、优势和局限性，并根据实际数据的特征做出明智的选择，是优秀工程师必备的核心能力。

掌握了计数排序和桶排序，你的算法工具箱又增添了两件利器。在下一篇文章中，我们将学习最后一种非比较排序算法——基数排序，它巧妙地结合了计数排序的思想来处理更大范围的整数排序问题。敬请期待！

乐奇 Rokid 开放社区

更多推荐

智能眼镜新品扎堆：AR、VR、MR到底怎么分？

乐奇 Rokid 开放社区

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精