波仔
🧮 第5章 排序算法
📄 一句话概括

冒泡是换邻居：每一轮把最大的往右挤，挤到头就定住一个。 插入是挪空位：左边始终有序，新来的从右往左找位置，比它大的全往右挪一格。 两者最坏都是 28 次比较，但数据接近有序时插入更快——只比了 20 次。

📝 本章和前面几章的关系

上一篇的两个算法一个是「不比较」，一个是「比满」；这一篇的两个是「边比边换」。 冒泡和插入是初学最先遇到的两个，也是理解 O(n²) 最好的样本。 这一篇还有一个小结论值得记住：真实数据常常已经大致有序，这时插入排序最快。

一、冒泡：大的往右挤

第一轮：5 和 3 比，换；5 和 8 比，不换；8 和 4 比，换……一路下来，最大的 8 被挤到最右边。 第二轮再从左边开始，这次最大的变成 7，也被挤到右边第二位。 演示里七轮的过程可以对照：每轮结束后，右边那一段就多一个定住的数。

所以它和选择排序其实是同一个骨架：每轮搞定一个位置。区别在选择排序是「先找到再换一次」， 冒泡是「一路换过去」。 这也解释了为什么冒泡交换多（16 次）：它靠交换来移动，而不是找到位置后换一次。

二、冒泡唯一的优化：一次都没换就收工

演示里第 7 轮打印出来和上一轮一样，注解写着「这一轮一次都没换，说明已经有序，提前收工」。 这是冒泡唯一值得加的优化：某一轮如果一次交换都没发生，就可以直接停。 为什么？因为一整轮没换，说明每一对相邻的数都已经是大在前小在后——已经有序了，再跑也没用。

这个优化带来的好处很实在：数据本来就排好时，它只跑一轮，比较 n-1 次就完， 复杂度从 O(n²) 掉到 O(n)。 但也只有这一种情况有用。数据是倒序的时候，它还是要比满 28 次，而且每次比较都要换。

三、插入排序：像整理手里的牌

打牌时你怎么整理手牌？新摸一张，插到已经排好的那几张里合适的位置。 插入排序就是这个动作：左边一段始终有序，每来一个新数，就在这段里从右往左找位置， 比它大的都往右挪一格，然后把它放进去。 演示里八轮的过程，每一轮左边那段都比上一轮长一个，且始终有序。

注意它标的是「挪动 16 次」而不是「交换 16 次」——因为它的动作是挪，不是两两交换。 这个区别在记录很大时很重要。 插入排序还有个好处：它可以在数据边到边排。不用等全部数据到齐才开始，来一条插一条。 这一点别的排序做不到。

四、三个比一比

把选择、冒泡、插入放在一起，同一批八个数：

算法 比较次数 交换／挪动 数据已有顺序时
选择排序 28 次 6 次 没变，还是 28 次
冒泡排序 28 次 16 次 1 轮 7 次就停
插入排序 20 次 16 次 7 次，一次都不用挪

最坏情况下三者都是 28 次比较——这就是 O(n²) 的样子：数据翻倍，步数翻四倍。 但这批数据里插入只比了 20 次。为什么？ 因为它一路上都处在「前面一段已经排好」的状态里，很多比较第一次就成功了。 选择排序不管数据长什么样都比满 28 次。它没有「提前高兴」的余地。

所以三者的差别不在最坏情况（都一样），在数据接近有序的时候。

五、为什么标准库小数据会退回插入排序

真实业务里的数据常常已经大致有序——只补了几条、只改了几个值。 这种时候插入排序最快：每个新数几乎不用挪，比一次就找到了位置。 所以很多标准库的做法是：数据量小的时候直接上插入排序，数据量大才换快排或归并。

为什么小数据要特殊对待？ 因为快排、归并都有额外的开销（递归、临时数组），数据量小的时候这些开销比省下来的比较还多。 这条经验值得记住： 没有全局最优的算法，只有分段最优的策略。真实的排序实现几乎都是「几个算法混着用」。

六、动手 Demo：冒泡换邻居、插入挪空位，各数一遍

先用冒泡排八个数，把每一轮的结果打出来，注意第 7 轮没有变化。 再用插入排序排同一批数，看左边那一段怎么一点点变长。 两个都数清比较次数和交换次数。

a = [5, 3, 8, 4, 2, 7, 1, 6]

b = a[:]
cmp_cnt = swap_cnt = 0
for i in range(len(b) - 1):
    changed = False
    for j in range(len(b) - 1 - i):
        cmp_cnt += 1
        if b[j] > b[j + 1]:
            b[j], b[j + 1] = b[j + 1], b[j]
            swap_cnt += 1
            changed = True
    print('冒泡第', i + 1, '轮', b)
    if not changed:
        break
print('比较', cmp_cnt, '交换', swap_cnt)

c = a[:]
cmp2 = move2 = 0
for i in range(1, len(c)):
    key, j = c[i], i - 1
    while j >= 0:
        cmp2 += 1
        if c[j] > key:
            c[j + 1] = c[j]
            move2 += 1
            j -= 1
        else:
            break
    c[j + 1] = key
    print('插入第', i + 1, '个', c)
print('比较', cmp2, '挪动', move2)

实跑输出：

--------------------------------------------------------------------
冒泡排序与插入排序
--------------------------------------------------------------------


  ① 冒泡：大的往右挤
  --------------------------------------------------------------------
  初始：[5, 3, 8, 4, 2, 7, 1, 6]
  第 1 轮：[3, 5, 4, 2, 7, 1, 6, 8]
  第 2 轮：[3, 4, 2, 5, 1, 6, 7, 8]
  第 3 轮：[3, 2, 4, 1, 5, 6, 7, 8]
  第 4 轮：[2, 3, 1, 4, 5, 6, 7, 8]
  第 5 轮：[2, 1, 3, 4, 5, 6, 7, 8]
  第 6 轮：[1, 2, 3, 4, 5, 6, 7, 8]
  第 7 轮：[1, 2, 3, 4, 5, 6, 7, 8]
  这一轮一次都没换，说明已经有序，提前收工
  比较 28 次，交换 16 次
  每一轮把最大的那个「冒」到最右边，像水里的气泡浮上来。
  那句「一次都没换就提前收工」是冒泡唯一的优化点：数据本来就有序时，它只跑一轮就停，变成 O(n)。

  ② 插入：像整理手里的牌
  --------------------------------------------------------------------
  初始：[5, 3, 8, 4, 2, 7, 1, 6]
  第 2 个 3 插进去：[3, 5, 8, 4, 2, 7, 1, 6]
  第 3 个 8 插进去：[3, 5, 8, 4, 2, 7, 1, 6]
  第 4 个 4 插进去：[3, 4, 5, 8, 2, 7, 1, 6]
  第 5 个 2 插进去：[2, 3, 4, 5, 8, 7, 1, 6]
  第 6 个 7 插进去：[2, 3, 4, 5, 7, 8, 1, 6]
  第 7 个 1 插进去：[1, 2, 3, 4, 5, 7, 8, 6]
  第 8 个 6 插进去：[1, 2, 3, 4, 5, 6, 7, 8]
  比较 20 次，挪动 16 次
  左边一段始终是有序的，每来一个新数，就在这段里从右往左找位置，比它大的都往右挪一格，
  然后把它放进去。

  ③ 三个比一比
  --------------------------------------------------------------------

| 算法 | 比较次数 | 交换／挪动 | 数据已有顺序时 |
|---|---|---|---|
| 选择排序 | 28 次 | 6 次 | 没变，还是 28 次 |
| 冒泡排序 | 28 次 | 16 次 | 1 轮 7 次就停 |
| 插入排序 | 20 次 | 16 次 | 7 次，一次都不用挪 |

  三者在最坏情况下都是 28 次比较——这就是 O(n²) 的样子：数据翻倍，步数翻四倍。
  这批数据里插入排序只比了 20 次，因为它一路上都处在「前面一段已经排好」的状态里。
  选择排序不管数据长什么样，都比满 28 次。
  差别在「数据接近有序」的时候。
  真实业务里的数据常常已经大致有序（只补了几条），这时插入排序反而最快，
  所以很多标准库在数据量小的时候会退回插入排序。

①冒泡内层是 range(len(b) - 1 - i)，因为右边 i 个已经定住了，不用再比。 这就是它比「每轮都比满」少一点的原因。 ②changed 这个开关就是那句「一次都没换就收工」。没有它，第 7 轮还是会跑。 ③插入排序的 while 里，c[j + 1] = c[j] 是挪动不是交换——它只把大的往后挪一格，新数最后才落地。 ④最后两组数：冒泡 28 比较 16 交换，插入 20 比较 16 挪动。比较次数的差别就是这一篇的重点。

30 秒实验

  1. 把数据换成已经排好的 [1..8]，看冒泡跑几轮、插入比几次。
  2. 把数据换成倒序 [8..1]，看两个算法各比几次、各换几次。
  3. 把冒泡的 > 改成 >=，看稳定性会不会变（提示：相等的两个数会不会被换）。

常见误区

  1. 「冒泡和插入是一样的，都是 O(n²)。」最坏一样，但接近有序时插入快得多。
  2. 「冒泡每轮都比满。」右边定住的不用再比，而且一次没换就能提前停。
  3. 「插入排序要交换。」它是挪动，不是两两交换，记录大时更省。
自测三问（点开对答案） 1. 冒泡排序每一轮在做什么？ —— 从左边开始两两比较，大的往右换，一轮下来最大的被挤到最右边。 2. 冒泡唯一的优化是什么？ —— 某一轮一次交换都没发生就停——说明已经有序。数据本来有序时复杂度降到 O(n)。 3. 为什么插入排序在这批数据上只比 20 次？ —— 它左边始终有序，很多新数比一次就找到了位置，不用一路比到底。

三个算法都是 O(n²)，八个数看不出差距，但一千个数就要五十万次。 下一节请出第一个真正快的：先分到不能再分，再合回去。

相关笔记