算法与理论计算机2021arxiv.org
这是最简单（也最令人惊讶）的排序算法吗？
Is this the simplest (and most surprising) sorting algorithm?
入门 · 约 20 分钟读完前置知识：基础编程、排序算法、数学归纳法
导读
这篇论文讨论一个极简却反直觉的双重循环排序算法：内层循环把当前元素与整个数组比较并在必要时交换，外层循环依次处理每个位置。作者证明它确实能完成排序，并用不变量/归纳解释其正确性，时间复杂度为 O(n^2)。论文的重点不是提出更快的排序，而是说明一个看起来几乎不可能正确的简单过程为何会奏效。
HN 关注点：HN 读者被“如此简单、甚至像错误代码的算法竟然可证明正确”吸引，讨论还延伸到它是否被多次独立发现、与 exchange sort 的区别，以及自动程序搜索能否发现这类算法。
HN 评论精选
这几条评论里：补充 2 亲历 1
补充给出该算法正确性的高层不变量/归纳解释：内层循环逐步扩展已排序前缀。
高层次的排序原因：内层循环接收数组和下标 i，把最大值放到位置 i；并且如果 i 之前的子数组已排序，那么处理后到 i 的子数组也会有序。外层循环让 i 从 1 到 n，单个元素显然有序，再靠内层循环的“扩展有序性”，2、3、…、N 的子数组依次有序。内层循环具有这个性质可分两种情况：若第 i 个元素已大于前面所有元素，它不会动前面的元素，只可能让第 i 个元素更大，因此有序性扩展到 i；若第 i 个元素小于前面某个元素，它会从那个较小元素开始一路交换到下标 i，把原来的第 i 个元素插入到有序位置，之后即使改变第 i 个元素和后面的元素，有序性仍保持。
dilap查看英文原文
High level description of why it sorts: The inner loop takes an array and an index i in the array, and rearranges the array to put the largest value at index i. This is done in such a way that if the sub-array up to but not including i is sorted, then afterwords the sort will be extended such that the sub-array up to and including i will be sorted. The outer loop says, just call in to the inner loop with i from 1 to n. This will result in a sorted array, because the initial array of a single element is trivially sorted, and then we'll have by the sort-extension property of the inner loop that the progressively larger sub-arrays of 2, 3, ... up to N elements become sorted. You can see that the inner loop has the sort extension property by thinking about two cases. Case 1: If the i-th element is already larger than all previous elements, it won't touch any of the elements before i, and will only potentially make the i-th element bigger, thus clearly extending the sort though the i-th element. Case 2: If the i-th element is smaller than one of the previous elements, it won't touch any elements until reaching that smaller element; then it will start a series of swaps until it reaches index i, at which point the the original value of the i-th elment is left inserted in sorted position into the sub-array up to and including i. So at this moment we have the sort extension property. From there, it may increase the value of the i-th element and change later elements, but of both those will preserve the sub-array sort.
亲历指出论文算法与他熟悉的 exchange sort 不同，并补充 exchange sort 与 Catalan 数的意外联系及自己的独立发现经历。
编辑：我快速看了论文后跑题了；下面说的是另一个叫 exchange sort 的算法及其有趣性质。论文里的算法其实不同，而且更令人意外。嘿，那也是我的排序算法！我肯定它被独立发现过很多次，但其中一次是我在还不知道 O(n log n) 排序之前发现的；我用过很多次，包括 INOI 2004 编程竞赛。2011 年我在 math.SE 问过这个算法与 Catalan 数的关系，这是一个论文没提到的意外性质。对于二次时间够用的场景，我通常写：for i = 1 to n: for j = i+1 to n: if a[i] > a[j]: swap(a[i],a[j])。它看起来像冒泡排序，但更接近选择排序。容易看出为什么有效：外层每轮把 a[i] 设为 a[i…n] 中的最小元素。另外，我曾给以《Enumerative Combinatorics》闻名的 Richard Stanley 教授发邮件，问他这是否与他的 Catalan Numbers 清单中的问题有关；他当时不知道有直接联系。
svat查看英文原文
[Edit: I took a quick glance at the paper and got carried away; the rest of this comment is about a different algorithm apparently known as "exchange sort", and an interesting property of it. The algorithm in the paper is actually different, and indeed more surprising.] Hey! That's my sorting algorithm! (Well, I'm sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: https://math.stackexchange.com/questions/36022/how-do-the-catalan-numbers-turn-up-here > For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following: //Given array a[1], ... a[n] for i = 1 to n: for j = i+1 to n: if a[i] > a[j]: swap(a[i],a[j]) > It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, `a[i]` is set to be the smallest element of `a[i…n]`. ---- Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?): > > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left] > Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423. > Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412. > Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples). And 14 is C_4, the fourth Catalan number.
补充补充 2015 年 StackExchange 上已有同样问题与不变量解释，说明该算法可能被多次独立发现，并感叹信息检索/自动程序搜索。
我记得 2015 年在 Stack Overflow 网站问过这个问题。有人成功用论文里同样的不变量回答了。我记得是通过自动程序搜索发现这个程序的，所以这个算法和它为何工作的问题可能已被发现很多次。要是有什么能让我们从海量数据中浮现信息就好了……
GistNoesis查看英文原文
I remember asking the question on a stack-overflow site in 2015. https://cs.stackexchange.com/questions/45348/why-does-this-sort-algorithm-work And it was answered successfully by pointing the same invariant they point in the paper. I remember finding this program through via automatic program search, so the algorithm and the question of why it works as probably been discovered many times. If only we had something that would allow to surface information from the vast amount of data available...
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2021Hacker News 讨论帖615 分 · 313 评
- 2025Hacker News 讨论帖130 分 · 118 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选