第 07 章

排序算法的战争——一个年轻人躺在莫斯科的沙发上，改变了计算机世界

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1945—2002年 · 归并排序、快速排序、堆排序与现代混合排序1959—1960年前后，莫斯科。一位年轻的英国人，躺在莫斯科国立大学宿舍的沙发上。他正在思考一个工作中遇到的问题：怎样把一句俄语中的单词，按照字母顺序排列？他想到一种方法。但很快意识到，这种方法太慢。他又想到另一种方法。这一次，他没有沿着相邻元素一个个比较，而是设想：假如能把一组数据分成两部分，让左边所有元素都小于右边所有元素，是不是就可以分别处理这两部分？这个想法后来成为计算机科学中最著名的排序算法之一。它叫作 Quicksort，快速排序。而当时躺在沙发上的年轻人，是 Tony Hoare。不过，这场故事还藏着几个更加有趣的情节：

Hoare 有了算法思想，却一度写不出完整程序。
回到英国后，他的上司不相信他有更快的排序方法，甚至和他打了一个六便士的赌。
一种早在1945年便出现的排序方法，后来成为快速排序最重要的竞争对手之一。
1991年，贝尔实验室的工程师发现，已经广泛使用几十年的快速排序实现，竟然可能把几分钟的任务拖成几周。

这不是四种算法的简单比较，而是一场持续半个多世纪的技术竞争。

第一幕：1945年，计算机还没成熟，排序已经成为一场重要实验

故事先从 John von Neumann（约翰·冯·诺依曼）开始。1945年，第二次世界大战接近尾声。电子计算机正在从专用计算设备，走向可以通过程序执行不同任务的通用机器。但当时的研究者面对的问题，并不只是怎样制造更快的计算电路。他们还必须回答：一台计算机究竟需要怎样的指令，才能表达复杂的程序？加法和乘法很容易理解。但排序不同。排序要求计算机反复比较、判断、交换或移动数据，并根据中间结果决定下一步动作。它是检验计算机指令系统与程序设计能力的一个很好的问题。

冯·诺依曼为什么研究排序？

1945年，冯·诺依曼为 EDVAC 的指令系统研究编写了早期归并排序程序。根据 Donald Knuth 对早期计算机排序史的整理，冯·诺依曼使用归并排序检验正在研究的计算机指令体系能否方便地表达组合性的决策过程。当时还有一个很实际的背景：穿孔卡片排序设备已经是成熟技术，计算机的排序能力可以与这些专用设备比较。^{[bitsavers.computerhistory.org]}也就是说，归并排序在早期电子计算机历史中扮演过一个非常特别的角色：它既是处理数据的算法，也是检验计算机体系结构的一项实验。

归并排序最巧妙的地方：两个有序序列很好合并

假设现在有两组数字：

序列 A

序列 B

我们需要合并成一个有序序列。如果两个序列本来就已经有序，根本不需要把所有元素重新比较一遍。只要观察两边最前面的元素：2 和 1，先取1。2 和 4，先取2。5 和 4，先取4。依此类推。最终得到：1、2、4、5、7、8

归并实验：一步步合并

实验一：Merge 操作0 / 6

左序列

右序列

合并结果

每次只比较两个序列当前的首个未取出元素，然后把较小的移入结果。

但你可能马上发现一个问题。刚才的两个序列本身就是有序的。如果原始数据是完全无序的呢？例如：8、3、7、2、9、1、5、4那就先不断拆分，直到每一组只有一个元素。因为单个元素天然有序。

查看 SVG 配图原件

07-003.svg · 点击查看大图

每一层的合并总工作量都是

O(n)

。而分成两半之后，递归深度约为

\log_2n

。因此：

T(n)=2T(n/2)+O(n)

得到：

\boxed{T(n)=O(n\log n)}

归并排序的最大优势之一，是无论数据原本怎样排列，比较排序版本都能保证

O(n\log n)

的最坏时间复杂度。但典型的数组归并排序需要额外的

O(n)

辅助存储空间。在早期计算机内存非常宝贵的环境下，这一点就变得重要了。于是，接下来的故事里，一个年轻人提出了另一种设计路线。

第二幕：1960年，莫斯科国立大学的一张沙发

Tony Hoare

1934—2026 · 英国计算机科学家 · 1980年图灵奖得主快速排序的发明者，也是程序逻辑、形式化验证、并发计算等领域的重要开拓者。

Hoare 最初并不是一位专门研究排序的算法理论家。他在牛津大学学习古典学，并对逻辑、语言和数学产生了浓厚兴趣。后来，他前往苏联学习俄语，并参与机器翻译相关研究。当时人们已经开始尝试让计算机把一种语言转换为另一种语言。这个目标甚至在今天仍然需要复杂的人工智能系统才能很好完成。而1950年代的机器翻译系统，许多基础工作还必须通过相对简单的规则和词典来完成。

一卷磁带，带来了怎样的麻烦？

假设有一句俄语：

Машина переводит текст.

意思大致是：“机器翻译文本。”为了翻译这句话，计算机需要查找不同单词在俄英词典中的对应项。问题是，当时的大型词典可能存储在磁带上。

磁带是一种顺序访问设备。它不像内存，可以立即随机访问任意位置。如果第一次要找字母靠后的词，下一次又要找字母靠前的词，就可能需要重新定位磁带。于是 Hoare 发现：既然词典已经按照字母顺序排列，为什么不先把要查询的单词也排序？这样就能沿着词典顺序查找多个单词，减少反复定位磁带的需求。这是他后来在访谈中明确讲过的技术背景。^{[Computer Science][Hoare,Tony transcript of the interview.doc]}

第一种想法：一个一个插入

这里有一个重要的历史细节。在不同的回忆中，Hoare 对最初想到的平方级排序方法有过不同表述。一次较早的访谈，他说最初的想法类似冒泡排序。而在2015年的回忆中，他明确称最初想到了插入排序。我们能确定的是：他首先考虑了一种需要平方级工作量的方法，随即意识到它太慢了。^{[anothercasualcoder.blogspot.com][Hoare,Tony transcript of the interview.doc]}假设有一万个单词。如果算法的操作次数以

n^2

增长，那么：

n^2=100,000,000

这个规模就可能相当可观。当然，这不意味着程序一定要执行整整一亿次比较，具体次数取决于算法和输入。但 Hoare 已经看到了问题：继续沿着逐个比较和调整的路线，似乎无法获得足够好的增长规律。于是他开始设想：我能不能先不管数据内部有没有排好序，只把所有元素分成大小有序的两组？这是快速排序真正的诞生时刻。

第三幕：那个改变一切的想法——Partition

假设有一组数字：8、3、7、2、9、1、5、4我们选择5作为基准值（Pivot）。然后只做一件事：让小于5的元素集中到左边。大于5的元素集中到右边。例如，第一轮分组结果可以是：

一次分区完成后

3

2

1

4

5

8

9

7

小于5Pivot = 5大于5

注意左边的：3、2、1、4还没有排好序。右边的：8、9、7也没有排好序。但我们已经获得了一个重大成果。左边任何一个元素，都比右边任何一个元素小。于是整个问题变成：对左边再做一次相同操作。对右边再做一次相同操作。不断重复。直到子数组只剩下零个或一个元素。这就是分治：Divide and Conquer。不过，Hoare 面临一个新问题。

想到了算法，为什么却写不出程序？

在当时，他掌握的编程语言是 Mercury Autocode。他已经能够构思分区操作，也能够理解接下来要处理多个尚未排序的子区间。但是，怎样管理这些不断产生的待处理区间？这正是递归和调用栈能够解决的问题。Hoare 后来回忆，当时他没能成功完成整个程序。直到接触支持递归过程的 ALGOL 60 后，他才更顺利地实现了算法。^{[anothercasualcoder.blogspot.com][cs.stanford.edu]}还记得第二章《栈与递归》吗？当时我们讲：

调用栈可以记住一个尚未完成的任务，等内部子任务结束后，再返回原来的位置。

现在你终于看到它在真实算法发明史上的重要性。没有递归，快速排序并不是无法实现；显式栈同样可以管理待排序的区间。但递归让这种算法思想得到了非常直接、自然的程序表达。

第四幕：回到英国，一场价值六便士的赌局

Hoare 回到英国之后，进入 Elliott Brothers 工作。这家公司当时生产自己的计算机。他需要为计算机实现软件，其中就包括排序程序。有一天，上司交给他一个任务：实现一种当时刚提出不久的排序方法——Shellsort（希尔排序）。希尔排序由 Donald Shell 于1959年发表。它通过逐渐缩小的间隔，对数据进行多轮整理，通常能够显著改善简单插入排序的性能。Hoare 完成了上司交代的工作。然后，他提出自己知道另一种更快的方法。在后来的口述历史中，Hoare 回忆说，上司并不相信，甚至以六便士打赌。于是 Hoare 解释了他的算法。上司将其用于 Elliott 的计算机，结果发现性能确实非常出色。尤其有意思的是，Hoare 回忆，上司之前还使用过归并排序，而新的算法在相关测试中表现得更快。^{[Hoare,Tony transcript of the interview.doc]}这一情节有特别高的历史价值，因为它来自发明者本人，而不是后人编造的传奇。

接下来发生了什么？

1959—1960年前后： Hoare 在莫斯科形成快速排序的核心思想。
1961年： 他在 Communications of the ACM 发表了 Partition、Quicksort 和 Find 三个相关算法。
1962年： 他在 The Computer Journal 发表更完整的论文 Quicksort。
1980年： Hoare 获得 ACM 图灵奖，表彰其在程序语言设计和定义等方面的重大贡献。

论文发表记录由牛津大学及期刊档案确认。^{[牛津大学计算机科学系][Oxford Academic]}

原始的1962年论文非常值得一读。它不是一本长篇专著，而是一篇篇幅不长的技术论文。然而，这短短几页，却对后来的算法教学与实际编程产生了极大的影响。阅读 Hoare 1962年论文《Quicksort》的原始期刊页面

第五幕：快速排序真的快吗？亲自当一次 Hoare

我们现在做一场实验。有七张卡片：9、2、7、4、8、1、5规则是：选择最后一个元素5作为 Pivot。把小于5的元素放到左侧，大于5的元素放到右侧。然后递归地处理两边。这里使用一种简化的三路构造演示，而不是复刻 Hoare 1961年原始代码中的具体交换步骤。

快速排序实验室

Partition → Recursive Sort

步骤 1/4

原始数据。选取5作为第一次分区的基准。

用 Python 实现这个思想

先看一种特别容易理解的写法：

def quicksort(nums):
    if len(nums) <= 1:
        return nums

    pivot = nums[len(nums) // 2]

    left = [x for x in nums if x < pivot]
    middle = [x for x in nums if x == pivot]
    right = [x for x in nums if x > pivot]

    return (
        quicksort(left)
        + middle
        + quicksort(right)
    )

它的逻辑很清楚：

选择基准。
把数据分成小于、等于、大于基准的三组。
递归排序左右两组。
合并最终结果。

但要注意：这是教学用的三路、额外分配列表的版本，并非原地快速排序。Hoare 的快速排序之所以受到早期程序员青睐，一个重要原因正是它可以在数组内部交换元素，避免归并排序所需的大型辅助数组。

第六幕：快速排序的致命缺陷

现在我们尝试一种非常不友好的输入：1、2、3、4、5、6、7、8假设某个简单版本总是选择第一个元素作为基准。那么第一轮：左边0个，右边7个。第二轮：左边0个，右边6个。第三轮：左边0个，右边5个。你发现什么了？算法根本没有把问题有效地拆成两半。分治退化了。

比较次数会怎样增长？

对于这种版本，最坏情况下比较次数类似：

(n-1)+(n-2)+\cdots+1

因此：

\frac{n(n-1)}2

于是时间复杂度退化为：

\boxed{O(n^2)}

实验：好的分区与坏的分区

元素数量 n

256

均衡分区的增长量参考2,048

极端失衡的比较次数32,640

绿色使用 n log₂n 作为增长量参考，不代表某个具体实现的精确比较次数；橙色对应每轮只确定一个元素的极端情形。两者刻度相同。

如果基准值每次恰好把问题分成相近的两部分，那么：

T(n)=2T(n/2)+O(n)

得到：

O(n\log n)

但如果每次几乎只减少一个元素：

T(n)=T(n-1)+O(n)

就会得到：

O(n^2)

问题因此变得很尖锐：归并排序最坏也只有 $O(n\log n)$ ，为什么程序员还要使用可能退化成 $O(n^2)$ 的快速排序？答案隐藏在内存访问、数据移动、常数开销和实际输入分布之中。在许多适合的数组排序场景下，原地快速排序具备较好的缓存局部性，数据交换数量和额外内存开销也有吸引力。理论最坏复杂度并不是衡量实际速度的唯一标准。而这场争论，后来还引出了另一个竞争者。

第七幕：1964年，一个新的排序算法从树中诞生

1964年，英国。一位名叫 J. W. J. Williams 的研究者，发表了一个新的算法。论文编号为 Algorithm 232。名字非常简洁：Heapsort，堆排序。更有意思的是，Williams 当时也在 Elliott Brothers 工作，也就是 Hoare 曾经任职的公司。但不要因此把两人的算法发明过程直接描绘成面对面的竞赛；现有史料支持他们在这一时期的公司联系，却不足以证明存在这样的个人竞争场景。Williams 的算法发表于1964年6月的 Communications of the ACM。同年12月，Robert W. Floyd 发表了相关改进，推动了更高效的堆构造方法。^{[算法第四版][xlinux][Bitsavers]}

堆排序想解决什么问题？

它试图结合两种优点：

像快速排序一样，不需要一个与输入等长的辅助数组。
像归并排序一样，保证最坏情况下的 $O(n\log n)$ 排序时间。

而它使用的工具，来自上一章的树结构。

堆到底是什么？

假设有一棵树：

             9
           /   \
          7     8
         / \   / \
        2   4 1   5

这里每个父节点都不小于自己的孩子。因此它是一个最大堆（Max Heap）。它并不要求整棵树的每一层从左到右完全有序。但有一个非常重要的保证：根节点一定是整个堆中的最大值。于是，我们可以：先把最大值9移到数组末尾。剩余元素恢复堆结构。再取出最大值8。接着7。不断重复。最终，数组就排好序了。

为什么数组也能表示一棵树？

对于从0开始的数组下标：

\text{left}(i)=2i+1

\text{right}(i)=2i+2

\text{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor

这意味着，堆虽然逻辑上是一棵完全二叉树，却可以直接保存在连续数组中，而不需要为每个节点建立左右指针。

树形结构与数组表示

查看 SVG 配图原件

07-008.svg · 点击查看大图

数组按照层序保存完全二叉树，因此节点关系可以直接由下标计算。

堆排序的效率为：

O(n\log n)

而使用自底向上的建堆方法，建堆本身只需要

O(n)

。这也是 Floyd 在相关算法发展中非常重要的贡献。于是到了1964年，程序员已经有了三种各具优势的选择：

算法	最坏时间	典型额外空间	稳定性
归并排序	$O(n\log n)$	$O(n)$	可以稳定
快速排序	$O(n^2)$	平均 $O(\log n)$ 调用栈	通常不稳定
堆排序	$O(n\log n)$	$O(1)$	通常不稳定

这里的空间复杂度针对常见的数组实现。归并排序也存在其他变体，而快速排序在最坏分区下递归栈可能增长到

O(n)

。注意，稳定性（Stability） 指的是：如果两个元素排序键相等，它们原来的相对顺序是否保留。例如：张三(90分)、李四(80分)、王五(90分)按分数排序之后，若张三与王五的先后关系没有改变，就是稳定排序。这个性质在多字段排序中非常有用。

第八幕：1991年，贝尔实验室的一场排序事故

现在，故事从1964年跳到1991年。快速排序已经流行了很多年。C 语言库中的 qsort() 是无数工程师熟悉的函数。大家似乎已经习惯相信：调用标准库排序，通常就应该又快又可靠。但贝尔实验室的两位研究人员 Allan Wilks 和 Rick Becker，发现某个排序任务的耗时非常异常。正常情况下只需要几分钟的工作，却正在消耗大量 CPU 时间。根据后来 Jon Bentley 和 Douglas McIlroy 在论文中的记录，如果没有及时中止，这次运行可能持续数周。究竟出了什么问题？不是 CPU 坏了。也不是编译器无法运行。而是排序输入的数据排列方式，触发了 qsort 实现的极端低效情况。^{[gallium.inria.fr]}

凶手：一组看起来非常正常的数字

研究人员发现，一种类似管风琴形状的数据排列能够让某些快速排序实现严重退化。例如：1、2、3、4、5、6、7、6、5、4、3、2、1数值先上升，随后下降。这种输入后来常被称为 organ-pipe pattern。它本身完全合法。但某些 Pivot 选择策略会连续产生非常不平衡的分区。结果，快速排序一次次走进最坏情况。

一份改变工程实践的论文

1993年，Jon Bentley 和 M. Douglas McIlroy 发表：Engineering a Sort Function《设计一个排序函数》。他们并没有简单地说“快速排序不好”。相反，他们重新审视一份工业级排序实现应该如何设计。他们研究了更合理的基准采样方式、重复元素处理、小数组的排序策略，以及如何设计能够暴露缺陷的测试数据。新的实现不仅需要在随机数据上很快，还必须面对现实世界中那些并不随机的数据。例如，已经排好序的数据、大量重复元素，以及容易诱发恶劣分区的特殊排列。^{[gallium.inria.fr][Wiley Online Library]}阅读1993年原始论文《Engineering a Sort Function》我认为这段历史甚至比快速排序诞生本身还具有工程教育意义。因为它告诉我们：一个算法在论文里很优秀，不代表某个具体实现就能处理所有现实输入。性能不是只靠渐近复杂度决定的。测试也不能只靠随机数组。如果一个函数已经被全世界广泛使用，它的边界情况就更值得认真研究。

第九幕：2002年，Python 决定不再单独押注某一种排序

故事来到2002年。计算机早已不再是占据整个房间的大型机器。个人计算机越来越普及。程序员也不再需要亲自实现每一种排序算法。现在的问题变成了：一个通用编程语言应该为用户提供怎样的默认排序实现？它不仅要快，还要稳定、可靠，并且能够利用现实数据的特点。这时，Tim Peters 为 Python 开发了一种自适应稳定排序算法。它后来被称为 Timsort。2002年7月26日，Tim Peters 在 Python 的问题跟踪系统中提交了一份关于自适应稳定归并排序的补丁。随后几天，他不断测试、修改、记录不同输入上的比较次数与运行表现。这些当年的讨论和补丁至今仍可查阅。^{[Python tracker][python.org][Python tracker]}

Tim Peters 发现了什么？

现实世界的数据，往往并不是完全随机的。例如：某家公司员工信息，可能本来就按部门大致排列。电商订单可能已经按日期排序，只增加了少量新记录。一本通讯录可能只有几条记录的位置错了。如果排序算法无视这些已有顺序，把所有数据都当作完全混乱的数据处理，就浪费了信息。Timsort 的核心思路之一，是识别输入中已经有序的连续片段（Run）。然后高效地整理、合并这些片段。因此，它把归并排序的可靠性，与现实数据中的已有顺序结合起来。今天，在 CPython 中：

numbers = [8, 3, 7, 2, 9, 1, 5]

numbers.sort()

或者：

result = sorted(numbers)

都使用稳定的排序机制，并非简单调用传统的原地快速排序。不过，现代 CPython 的实现还经历过后续优化和演化，不能将今天的全部内部细节等同于2002年最初的 Timsort。这代表排序算法发展史的一次重要变化：不再执着于选择一个理论上最漂亮的算法，而是根据实际输入特点组合多种思想。

第十幕：排序算法的真正赢家是谁？

把几位历史主角重新放到一起。

1945 · 冯·诺依曼与归并排序通过拆分与合并，获得可靠的对数线性时间复杂度。它也成为早期电子计算机指令研究的一项重要实验。

1960—1962 · Hoare 与快速排序通过巧妙的分区减少额外存储和数据移动，在大量数组排序场景中展现出很高的效率。

1964 · Williams、Floyd 与堆排序使用二叉堆，在原地排序的同时保证最坏

O(n\log n)

时间。

1993 · Bentley、McIlroy 与工程化快速排序通过特殊输入测试、基准选择和分区优化，提高通用排序函数的实际可靠性。

2002 · Tim Peters 与 Timsort充分利用输入中已有的有序片段，推动自适应稳定排序成为主流语言实现的重要选择。

实际上，没有一种算法彻底赢得了这场战争。

如果你需要稳定排序，而且希望保证最坏 $O(n\log n)$ ，归并排序家族非常有吸引力。
如果你要对内存中的数组进行高效原地排序，经过优化的快速排序仍然十分重要。
如果你特别看重最坏时间保证和较小额外空间，堆排序有独特价值。
如果你希望充分利用真实数据中的已有顺序，自适应混合排序可能更加合适。

而现代 C++ 的 std::sort 也常采用 Introsort（内省排序）一类混合策略：以快速排序为主，在递归深度过大时改用堆排序，并用插入排序处理小规模区间。具体实现由标准库决定。这就是为什么学习算法，不能只背复杂度表。

最后一次挑战：你会选择哪一种排序？

假设你是某数据库系统的工程师。现在需要对100万条学生记录按成绩排序。数据具有三个特点：

成绩相同的学生，必须保持原来的先后顺序。
数据原本已经大致有序。
额外内存可以适当使用。

你会优先考虑哪种排序？

普通原地快速排序传统堆排序稳定的自适应归并排序（如 Timsort）冒泡排序

尾声：从一张沙发，到数十亿次排序

1960年前后，Tony Hoare 躺在莫斯科国立大学宿舍的沙发上，思考如何让机器更高效地处理俄语单词。当时，他并不知道自己构思的算法会进入无数算法教材。也未必能预见，几十年之后，贝尔实验室的工程师还会为它设计更复杂的优化方法。1945年的冯·诺依曼、1964年的 Williams、1993年的 Bentley 与 McIlroy、2002年的 Tim Peters，也都在不同的硬件条件与软件需求下，重新思考同一个问题：怎样让大量数据按照我们需要的顺序排列，而且付出尽可能小的代价？有的人选择拆分再合并。有的人选择基准分区。有的人借助二叉堆。有的人研究现实数据本身已经存在的顺序。这场持续几十年的竞争，最终并没有诞生一位永远的冠军。相反，它让我们认识到：伟大的算法不只是让计算机执行更少的操作，更是找到一种与问题、数据和硬件相匹配的解决方式。

第七章知识总结

算法	平均时间	最坏时间	关键特点
插入排序	$O(n^2)$	$O(n^2)$	小数组、近乎有序时有优势
归并排序	$O(n\log n)$	$O(n\log n)$	稳定、可靠
快速排序	$O(n\log n)$	$O(n^2)$	分区、通常可原地进行
堆排序	$O(n\log n)$	$O(n\log n)$	原地、最坏时间有保证
Timsort	$O(n\log n)$	$O(n\log n)$	稳定、自适应

历史原始资料

ACM：Tony Hoare 口述历史访谈，包括莫斯科沙发、算法诞生以及六便士赌局。Hoare：《Quicksort》（1962），快速排序的早期正式论文。Bentley 与 McIlroy：《Engineering a Sort Function》（1993），真实工程故障与排序函数改进。Python 2002年 Timsort 原始开发记录，可查看 Tim Peters 的补丁与讨论。

下一章预告

第八章：动态规划——一位数学家为什么故意给自己的算法起了个模糊的名字？

20世纪50年代，美国 RAND 公司。一位数学家正在研究多阶段决策问题。他意识到：许多困难的问题，之所以计算起来异常昂贵，并不是因为每一步都很难，而是因为我们不断重复解决已经解决过的小问题。后来，他提出了 Dynamic Programming——动态规划。这位数学家叫作 Richard Bellman。关于这个名字为什么叫“动态规划”，他后来留下了一段颇有争议、也十分有趣的亲身回忆，其中还牵涉到当时美国国防研究机构的政治环境。下一章，我们会从 Bellman 的真实研究经历出发，逐步理解状态、状态转移、最优子结构和记忆化搜索，并亲自推导背包问题与最短路径问题。而我们真正要探索的问题是：为什么有些指数级复杂度的问题，只需要记住过去计算过的结果，就能变得容易得多？