一、希尔：先隔几个比，再一点点缩小间隔

先按间隔 4 分组：位置 0 和 4 一组、1 和 5 一组……组内比大小、必要时换。排完是 2 3 1 4 5 7 8 6。 再把间隔缩到 2 排一遍，得到 1 3 2 4 5 6 8 7；最后间隔 1（就是普通插入排序）排一遍，完成。 演示里一共比了 20 次—— 比插入排序自己的 20 次一样多，但这批数据不是最坏情况。真正的收益在数据更乱的时候。

为什么间隔大有用？因为一个数能一次跨好几格，很快落到大致的位置。 间隔缩到 1 时，数据已经差不多有序，插入排序只要挪几下。 所以它不是新算法，是「先做几遍粗排，再做一遍细排」。改进的是插入排序的处境，不是它的逻辑。

二、希尔排序的定位：不上不下

复杂度大约是 n 的 1.3 次方（这个数取决于间隔怎么取，教材给的是这个量级）。 比 O(n²) 好，比 O(n log n) 差。所以它常被当成「过渡方案」。 它的优点是额外内存只要 1 个位置，而且是就地排序，代码也短。嵌入式或者内存紧的场合它还挺实用。

它还有个毛病：不稳定。隔几个分组交换，同分的两个数很容易被换过位置。 所以真实工程里它出现得不多——要快有快排，要稳有归并，它夹在中间。

三、快速：挑一个基准，小的放左边

八个数，拿最后一个 6 当基准。走一遍，比 6 小的扔左边、大的扔右边。 演示结果：左 5 3 4 2 1，中间 6，右 8 7。 注意这一步做了什么：6 的位置从此定死了，以后再也不动它。 因为它左边全比它小、右边全比它大，它就该待在这儿。

然后对左边五个、右边两个各做同样的事，递归下去。 每层都是「走一遍」，一共 log2(n) 层，所以平均 O(n log n)。 和归并一样是两层结构，区别在归并是「先分再合」，快排是「边分边定」。 快排不用额外数组（只用递归栈），所以额外内存只要 log n 量级——这是它比归并受欢迎的一个理由。

四、快排的软肋：基准挑得不好

同一批数据，基准挑法不同，快慢能差一个量级：

第二行最坑：数据本来就排好了，你还按「拿最后一个」来分，每次左边都是 n-1 个、右边 0 个， 等于每次只搞定一个。 这时候它退化成了选择排序——最快的算法掉到最慢那一档。 为什么「数据已经有序」反而最坏？因为有序意味着最后那个永远是最大的，分区永远分不匀。 这就是「好数据」也能弄死一个算法的例子。

五、工程上靠随机化把最坏压下去

真实实现都不挑固定位置，而是随机取一个，或者取头、中、尾三个数的中位数。 随机化之后，「每次都挑到最差基准」的概率低到可以忽略——它没有消灭最坏情况，但让它几乎不会发生。 这一点值得记住：最快的算法也有最坏情况，工程上不是消除它，是让它罕见。

另外还有两个常见补丁：数据量小（比如少于 16 个）时退回插入排序； 递归太深时换堆排序——后者是标准库里的常见组合。 所以「快排」在真实代码里往往不是一个算法，是一套组合策略。 这和第 5.3 那句「分段最优」是同一句话。

六、一张总表，外加 2 的次方

七种排序放一起，这张表不用背，看三件事就够：

三件事：桶排序最快但要有范围；n² 的一类在数据大时会崩；n log n 的一类靠「分」省步数。 再记住三个 2 的次方，看复杂度时能立刻估量级：2 的 10 次方是 1024，2 的 20 次方约 105 万， 2 的 30 次方约 10.7 亿。 所以「一百万个数据分几层」这种问题，一眼能答：log2(100 万) 约 20 层， n log n 就是「二十个一百万」，两千万步。

这一招在估算时极好用——不用算精确值，能判断「这个方案会不会崩」就够了。

七、动手 Demo：希尔缩小间隔，快排挑基准分两边

先按间隔 4、2、1 各排一遍，看数据怎么一点点有序起来。 再用最后一个数当基准做一次分区，看基准怎么被定死。 最后把递归做完，顺便数一下希尔排序比了几次。

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

b = a[:]
cmp_cnt = 0
gap = len(b) // 2
while gap:
    for i in range(gap, len(b)):
        key, j = b[i], i - gap
        while j >= 0:
            cmp_cnt += 1
            if b[j] > key:
                b[j + gap] = b[j]
                j -= gap
            else:
                break
        b[j + gap] = key
    print('间隔', gap, '排完', b)
    gap //= 2
print('希尔比较', cmp_cnt, '次')

def qsort(x):
    if len(x) <= 1:
        return x
    pivot = x[-1]
    left = [v for v in x[:-1] if v < pivot]
    right = [v for v in x[:-1] if v >= pivot]
    return qsort(left) + [pivot] + qsort(right)
print('快排', qsort(a))

实跑输出：

--------------------------------------------------------------------
希尔排序与快速排序
--------------------------------------------------------------------


  ① 希尔：先隔几个比，再一点点缩小间隔
  --------------------------------------------------------------------
  初始：[5, 3, 8, 4, 2, 7, 1, 6]
  间隔 4 排完：[2, 3, 1, 4, 5, 7, 8, 6]
  间隔 2 排完：[1, 3, 2, 4, 5, 6, 8, 7]
  间隔 1 排完：[1, 2, 3, 4, 5, 6, 7, 8]
  比较 20 次
  间隔大时，一个数能一次跨好几格，很快落到大致的位置；
  间隔缩到 1 时，数据已经差不多有序，插入排序只要挪几下就完。
  这就是「改进的插入排序」：不是换了思路，是先做几遍粗排，再做一遍细排。

  ② 快速：挑一个基准，小的放左边，大的放右边
  --------------------------------------------------------------------
  初始：[5, 3, 8, 4, 2, 7, 1, 6]，拿最后一个 6 当基准
  分完之后：左 [5, 3, 4, 2, 1] ｜ 6 ｜ 右 [8, 7]
  这一步叫分区：走一遍，比基准小的扔左边，大的扔右边。基准的位置就定死了，以后不用再动它。
  然后对左边、右边各做同样的事，递归下去。
  每层都是「走一遍」，一共 log2(n) 层，所以平均 O(n log n)。

  ③ 快排的软肋：基准挑得不好
  --------------------------------------------------------------------

| 数据情况 | 基准挑法 | 层数 | 总步数 |
|---|---|---|---|
| 随机乱序 | 随便挑 | 约 log2(n) | n log n |
| 已经排好序 | 每次挑最后一个 | n 层 | n²（最坏） |
| 已经排好序 | 随机挑或取中间 | 约 log2(n) | n log n |

  第二行是最坑的：数据本来就排好了，你还按「拿最后一个」来分，每次左边都是 n-1 个、右边 0 个，
  等于每次只搞定一个——退化成了选择排序。
  所以真实实现都随机取基准，或者取头中尾三个数的中位数。
  这一点值得记住：最快的算法也有最坏情况，工程上靠随机化把它压下去。

  ④ 这一章所有排序，一张总表
  --------------------------------------------------------------------

| 算法 | 平均 | 最坏 | 额外内存 | 稳定 |
|---|---|---|---|---|
| 桶排序 | n + 范围 | n + 范围 | 范围大小 | 稳定 |
| 选择排序 | n² | n² | 1 | 不稳定 |
| 冒泡排序 | n² | n² | 1 | 稳定 |
| 插入排序 | n² | n² | 1 | 稳定 |
| 归并排序 | n log n | n log n | n | 稳定 |
| 希尔排序 | 约 n^1.3 | n² | 1 | 不稳定 |
| 快速排序 | n log n | n² | log n | 不稳定 |

  这张表不用背。要记的是三件事：桶排序最快但要有范围；n² 的一类在数据大时会崩；
  n log n 的一类靠「分」来省步数。

  ⑤ 顺便把 2 的次方记下来
  --------------------------------------------------------------------
  2 的 10 次方 = 1024（一千）
  2 的 20 次方 = 1048576（一百万）
  2 的 30 次方 = 1073741824（十亿）
  这三个数记住，看复杂度时能立刻估出量级：100 万个数据分几层？log2(100 万) 约 20 层。
  所以 n log n 就是「二十个一百万」，两千万步。

①希尔那段就是插入排序， 只把 1 换成了 gap——所有下标间隔都变成 gap。gap 为 1 时它退化成普通插入排序。 ②gap //= 2 让间隔从 4 到 2 到 1 到 0。到 0 循环结束，所以最后一定排过一遍间隔 1。 ③快排那段用了列表推导，看着不像「就地交换」，但分区的意思是一样的：小的进 left，大的进 right， 基准夹在中间。 ④v >= pivot 里的等号让相等的数走右边，这是为了不无限递归；代价是这种写法不保证稳定。

30 秒实验

1. 把快排的基准从 x[-1] 改成 x[len(x) // 2]，用已经排好的数据测，看递归深度。
2. 把数据换成 [1, 2, 3, 4, 5, 6, 7, 8]，跑希尔排序，比较次数变成多少？
3. 查一下你常用语言的排序函数，看它内部是不是「快排 + 插入排序」的组合。

常见误区

1. 「快排是最快的，所以任何情况都用它。」数据已排好又固定挑最后一个当基准，它会退化成 n²。
2. 「希尔排序是新算法。」它就是插入排序换了个间隔，gap 为 1 时完全一样。
3. 「n log n 一定比 n² 快。」数据量小的时候常数项说了算，插入排序常常反超。

排序讲完了。 下一章换个问题：不要求整批站好队，只要求从里面找出一个。从一个一个看，到每次砍一半， 再到一次就到位。

• ☐ （本篇完，下一篇 6.1 线性搜索与二分搜索）

相关笔记

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