一、桶排序：按值放进对应的桶

数据是 3 1 3 0 2 3 1 2，值都在 0 到 3 之间。 准备 4 个桶（编号 0 到 3），把每个数丢进对应编号的桶里，数一数每个桶里有几个：[1, 2, 2, 3]。 然后按桶的编号从小到大倒出来：0 一个、1 两个、2 两个、3 三个，得到 0 1 1 2 2 3 3 3。

整个过程一次比较都没有。数一遍、倒一遍，两步就完。 所以它比任何比较排序都快——这就引出一个结论： 如果不用比较就能定位置，那就比「靠比较来定位置」快一个档次。

二、桶排序的代价：必须先知道范围

桶排序的前提是「值落在 0 到 3 之间」。这个前提不成立，它就废了。

第二行最能说明问题：一百万个桶，实际只有八个数——空间全浪费在空桶上。 第三行是精度问题。金额有分有厘，硬要变成整数就得决定「保留到哪一位」，而这一步会丢东西。 所以桶排序是典型的空间换时间：用一大片额外空间，换掉全部比较。 空间便宜的时候划算，空间贵的时候不划算。

现实里的用法是「范围可控就用它」：百分制成绩、年龄、月份、星期，这类数据天生范围小。

三、选择排序：每轮挑一个最小的

换回八个数的数据。 选择排序的做法：第一轮扫一遍挑出最小的，放到第 1 位；第二轮在剩下七个里挑，放到第 2 位。 演示里七轮的过程可以对着看：第 1 轮挑出 1，第 2 轮挑出 2……每轮结束后，左边那一段就再也不会变了。 注意第 4 轮：挑出 4 之后数组没变。因为 4 本来就在第 4 位，不用换。

所以它有个特点：交换只在「挑出来的不是当前位」时才发生。这就是它只换了 6 次的原因。 「左边那段已经定死」这个性质很重要：它保证了算法正确——每轮之后，前 i 个位置就是最终答案。

四、28 次是怎么来的

第一轮比 7 次，第二轮 6 次，一路到 1 次：7+6+5+4+3+2+1 = 28。 公式是 n 乘 (n-1) 除以 2。八个数就是 8 乘 7 除 2 得 28。 n 一大，这个数就是「n 的平方的一半」。所以选择排序的复杂度写成 O(n²)。

这就是 O(n²) 的含义：数据翻倍，步数翻四倍。一千个数是五十万次， 一万个数是五千万次——很快就不能忍了。 注意它跟数据长什么样完全无关。哪怕数据本来就排好了，它照样比满 28 次。 这一点下一节会和冒泡、插入对比。

五、选择排序的长处是交换少

八个数只换 6 次，最多也不会超过 7 次——每轮最多换一次。 对比冒泡排同样一批数据要换 16 次。差了一倍多。 为什么这件事值钱？因为挪数据比比较贵：比较只读，交换要写回内存。 一条记录几百 KB 的时候，交换一次的代价能顶几十次比较。

所以真实场景里有一条经验：记录很大时，优先选交换少的算法。哪怕比较次数一样多。 这也是为什么「哪个排序最好」这个问题没有统一答案——得先知道你的数据是「比较贵」还是「挪动贵」。

六、动手 Demo：桶排序不比较，选择排序每轮挑一个

先用 4 个桶把 8 个数排好，看它一次比较都没有。 再用选择排序排同一批八个数，把每一轮的结果打出来。 最后数一下比较和交换各多少次。

a = [3, 1, 3, 0, 2, 3, 1, 2]
buckets = [0] * 4
for x in a:
    buckets[x] += 1
print('桶里各几个', buckets)
out = []
for v, c in enumerate(buckets):
    out.extend([v] * c)
print('倒出来', out)

b = [5, 3, 8, 4, 2, 7, 1, 6]
cmp_cnt = swap_cnt = 0
for i in range(len(b) - 1):
    m = i
    for j in range(i + 1, len(b)):
        cmp_cnt += 1
        if b[j] < b[m]:
            m = j
    if m != i:
        b[i], b[m] = b[m], b[i]
        swap_cnt += 1
    print(i + 1, b)
print('比较', cmp_cnt, '交换', swap_cnt)

实跑输出：

--------------------------------------------------------------------
桶排序与选择排序
--------------------------------------------------------------------


  ① 桶排序：按值放进对应的桶
  --------------------------------------------------------------------
  数据：[3, 1, 3, 0, 2, 3, 1, 2]（值都在 0 到 3 之间）
  准备 4 个桶，数一遍放进去：[1, 2, 2, 3]
  按桶顺序倒出来：[0, 1, 1, 2, 2, 3, 3, 3]
  一个循环数数，一个循环倒出来，两步就完。没有比较，所以它比任何比较排序都快。
  代价是要先知道「值的范围」。
  范围一宽就废了：数据是 1 到 100 万，就得准备一百万个桶，而实际只有 8 个数——空间全浪费在空桶上。

  ② 桶排序的边界
  --------------------------------------------------------------------

| 数据情况 | 合适吗 | 原因 |
|---|---|---|
| 0 到 100 的整数分数 | 合适 | 101 个桶，装得下 |
| 1 到 100 万的学生学号 | 不合适 | 空桶太多 |
| 带小数的金额 | 不合适 | 要先量化成整数，会丢精度 |


  ③ 选择排序：每一轮挑一个最小的
  --------------------------------------------------------------------
  初始：[5, 3, 8, 4, 2, 7, 1, 6]
  第 1 轮：挑出 1 放到第 1 位  ->  [1, 3, 8, 4, 2, 7, 5, 6]
  第 2 轮：挑出 2 放到第 2 位  ->  [1, 2, 8, 4, 3, 7, 5, 6]
  第 3 轮：挑出 3 放到第 3 位  ->  [1, 2, 3, 4, 8, 7, 5, 6]
  第 4 轮：挑出 4 放到第 4 位  ->  [1, 2, 3, 4, 8, 7, 5, 6]
  第 5 轮：挑出 5 放到第 5 位  ->  [1, 2, 3, 4, 5, 7, 8, 6]
  第 6 轮：挑出 6 放到第 6 位  ->  [1, 2, 3, 4, 5, 6, 8, 7]
  第 7 轮：挑出 7 放到第 7 位  ->  [1, 2, 3, 4, 5, 6, 7, 8]
  比较 28 次，交换 6 次
  八个数，第一轮比 7 次，第二轮 6 次……加起来 7+6+5+4+3+2+1 = 28 次。
  公式是 n(n-1)/2，n 大了就是 n² 的一半。
  选择排序的好处是交换少：每轮最多换一次，八个数最多换 7 次。
  数据很大、挪动很贵的时候（比如每条记录几百 KB），这一点很有价值。

①桶排序那两段：一段数数（buckets[x] += 1），一段倒出来（[v] * c）。全程没有一次大小比较。 ②[v] * c 是「把 v 重复 c 次」，比写循环清楚。c 是 0 时正好得到空表。 ③选择排序第 4 轮打印出来和上一轮一样，因为 4 本来就在第 4 位，m != i 不成立，没有交换。 ④最后 28 次比较、6 次交换。28 是 7+6+…+1，跟数据内容无关。

30 秒实验

1. 把桶排序的数据换成 [30, 10, 30, 0, 20]，看要准备几个桶，代码怎么改。
2. 给选择排序的数据换成已经排好的 [1..8]，比较次数会变吗？
3. 想一下你们业务里哪些字段范围天生很小，能直接用桶排序。

常见误区

1. 「桶排序比选择排序高级，所以到处都能用。」要先知道范围，范围一宽就废。
2. 「选择排序每轮都交换。」只有挑出来的不是当前位时才换，所以 8 个数只换 6 次。
3. 「O(n²) 就是慢，没救了。」记录很大时它交换少，反而可能比别的实用。

桶排序要范围，选择排序比满 28 次。下一节请出两个更「自然」的排序：一个换邻居，一个挪空位。

• ☐ （本篇完，下一篇 5.3 冒泡排序与插入排序）

相关笔记

• 排序是什么
• 冒泡排序与插入排序
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引