算法与计算机科学arxiv.org
这是不是最简单（也最令人惊讶）的排序算法？
Is this the simplest (and most surprising) sorting algorithm?
2021 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇 arXiv 论文介绍了一个简单到令人惊讶的排序算法：它看起来像一段写坏的冒泡排序，却确实能正确地把数组排好序。论文用不变量解释了它为什么有效，并分析了其正确性与性能。评论区里多人表示自己也曾独立发现过这个算法。
为什么经久不衰：几行'看起来明显不对'的代码竟然是正确的排序算法，这种反直觉的例子既是绝佳的算法思维练习，也提醒人们判断代码对错要靠证明而非直觉，因此多年后仍值得一看。
HN 评论精选
从不变量角度解释算法为何正确：内层循环把有序前缀延伸一位，外层循环逐步扩大有序区间。
从高层解释它为什么能排序：内层循环接收数组和下标 i，重排数组把最大值放到位置 i，并且保证：如果 i 之前的子数组已有序，处理完后有序范围就延伸到包含 i。外层循环让 i 从 1 到 n 依次调用内层——单元素数组平凡有序，于是 2、3……直到 N 个元素的前缀逐渐变得有序。内层循环为何有这种'排序延伸'性质，可分两种情况：若第 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.
作者自称在学标准排序算法前独立发现过类似的'交换排序'，还发现它与卡塔兰数的惊人联系（并注明论文中的算法与之不同、更令人惊讶）。
嘿！这是我的排序算法！（它肯定被独立发现过很多次，其中一次就是我在还没学过 O(n log n) 排序的时候。）我在包括 INOI 2004 竞赛在内的很多场合用过它，十年前还在 math.SE 上问过它与卡塔兰数的联系——那是个论文没提到的、真正惊人的性质。'平方时间也够用的场合，我通常用这个算法……它看起来像冒泡排序，其实更接近选择排序：外层每轮把 a[i] 设为 a[i…n] 的最小值。'另外，我曾写信问过组合数学名家 Richard Stanley，这算法是否与他列出的几百道卡塔兰数习题有关，他说当时不知道有直接联系……[编辑：我扫了一眼论文就写嗨了；上面说的其实是另一种叫'交换排序'的算法，论文里的算法确实不同，而且更令人惊讶。]
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 年在 CS StackExchange 上问过同样的问题，当时有人用论文里同样的不变量成功解答了。这个程序是我通过自动程序搜索找到的，所以这个算法和'它为什么有效'的问题大概已经被发现过很多次了。要是我们有什么工具能把海量已有数据中的这些信息浮现出来就好了……
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...
用类似计数/桶排序的思路在课程比赛中轻松击败了所有冒泡排序实现。
这事有点傻，但也算相关。1993 年我大三修数字电子课（含 68000 汇编），实验课比赛看谁给一组 x 到 y 之间的随机不重复数排序最快。我的获胜方案是：把一段 y−x 大小的内存清零，再按数值本身把每个数放进对应位置（'27' 放进第 27 个单元，'18' 放进第 18 个……），最后顺序打印所有非零单元。其他二十来个同学写的都是各种冒泡排序，还说我作弊，教授则维护了我的胜利，因为我没违反任何比赛规则……
beyondzero查看英文原文
This is silly but sort of relevant. During college junior year (1993) as a physics major I took a class in digital electronics (which included 68000 assembler programming). We had a lab contest to create the fastest sorting routine for a set of random unique numbers between x and y. I won the contest by setting to 0 a y-x register range of memory and then inserting each number into the range based on the number itself ("27" into register 27, "18" into register 18, etc.). Then I printed out all non-zero numbers in the range. The other 20 or so students did versions of bubble-sorting and called my solution a cheat. The professor defended my victory as I had not broken any of the rules of the contest...
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选