← 目录 / 算法文档 · 模块三简单排序 / 3.4 桶排序

3.4　桶排序

不比较，直接按数值"对号入座"——用空间换时间，换来一种完全不同的排序思路。

本页目录

①什么是桶排序
②基础写法：用数组直接统计
③代价：用空间换时间
④完整代码与对比

① 什么是桶排序

前面三种排序（冒泡、选择、插入）有一个共同点：都靠"两两比较"决定谁该排在前面。桶排序换了一个完全不同的思路——它根本不比较任何两个数，而是直接利用数值本身的大小，把每个数"扔"进对应的桶里，最后按桶的顺序把所有数倒出来，就是排好序的结果。

这其实就是 2.2 节"数组标记法"里统计出现次数的直接应用：开一个数组当"桶"，下标对应数值，每个桶记录这个数值出现了多少次。统计完之后，从头到尾扫一遍桶，每个桶里有几个数，就连续输出几次——自然就是从小到大排好的顺序。

② 基础写法：用数组直接统计

用数组 {7, 2, 9, 2, 5, 2, 9} 演示（数值范围是 0~9）：

C++ · 桶排序

        
          1void BucketSort(int arr[], int n, int maxValue)
2{
  vector<int> bucket(maxValue + 1, 0);  // 每个桶记录该数值出现的次数
  for (int i = 0; i < n; i++)
  {
      bucket[arr[i]]++;  // 这个数值对应的桶计数加一
  }
8
  int index = 0;
  for (int value = 0; value <= maxValue; value++)  // 按桶的顺序，从小到大倒出来
  {
      while (bucket[value] > 0)
      {
          arr[index] = value;
          index++;
          bucket[value]--;
      }
  }
19}

      

{7, 2, 9, 2, 5, 2, 9} —— 每个数直接"对号入座"进对应的桶

桶 2 里堆了 3 个（因为 2 出现了 3 次），桶 5、7 各 1 个，桶 9 有 2 个，其余桶是空的。按桶的编号从 0 到 9 顺序读出来：2 2 2 5 7 9 9——完全不需要做任何比较，排序就完成了。

📌

这正是 2.2 节统计字母出现次数那段代码的"翻版"——只是那里统计完只是用来"看一看次数"，这里统计完之后，把桶按顺序读出来，结果天然就是排好序的数组。同一个"用数组当统计表"的技巧，换一种使用方式，就从"统计工具"变成了"排序算法"。

③ 代价：用空间换时间

桶排序快得不可思议——只需要扫一遍原数组（统计），再扫一遍桶数组（按顺序倒出来），总共大约 n + maxValue 次操作，比前面几种排序的 O(n²) 快得多。但它有一个隐藏的代价：桶的数量取决于数值的范围，不是数据的个数。

⚠️

如果数值范围特别大，桶排序反而会很浪费。假设只有 5 个数，但它们的取值范围是 0 到 10 亿，按这一节的写法就要开一个 10 亿大小的桶数组——内存根本装不下，而且绝大多数桶都是空的，纯属浪费。桶排序只适合"数值范围本身不会比数据量大太多"的场景，比如给 0~100 分的考试成绩排序、给 1~6 点的骰子结果排序。

1000 个数 —— 数值范围大小对桶排序的影响

范围 0~100

约1100次

范围 0~10亿

开不出这么大的数组

数据量同样是 1000 个，数值范围是 0~100 时桶排序又快又省，范围一旦变成 0~10亿，所需要的桶数组大小会直接超出内存限制——这正是桶排序"用空间换时间"必须权衡的地方：空间够、范围小，桶排序是神器；空间不够、范围大，桶排序根本用不了。

④ 完整代码与对比

排序方式	核心操作	时间复杂度	额外空间
冒泡 / 选择 / 插入	两两比较、挪动	O(n²)	几乎不需要
桶排序	按数值直接归位，无需比较	O(n + maxValue)	O(maxValue) 大小的桶数组

🎯

桶排序是模块三里唯一一个不靠比较的排序算法——这种"不比较、直接按值归位"的思路非常重要，后面学到的很多统计类问题（比如找出现次数最多的数、给数据分段统计）都用得到。但也正因为它依赖数值范围，桶排序不是万能的：碰到范围很大、或者数据是小数、字符串这类"不能直接当数组下标"的情况，就需要用回前面比较类的排序，或者把数据先"映射"到一个小范围（这个技巧叫离散化，会在模块十五详细介绍）。

1	void BucketSort(int arr[], int n, int maxValue)
2	{
3	vector<int> bucket(maxValue + 1, 0); // 每个桶记录该数值出现的次数
4	for (int i = 0; i < n; i++)
5	{
6	bucket[arr[i]]++; // 这个数值对应的桶计数加一
7	}
8
9	int index = 0;
10	for (int value = 0; value <= maxValue; value++) // 按桶的顺序，从小到大倒出来
11	{
12	while (bucket[value] > 0)
13	{
14	arr[index] = value;
15	index++;
16	bucket[value]--;
17	}
18	}
19	}