I Can't Believe It Can Sort:最简排序算法

Stanley P. Y. Fung 提出了一种名为 I Can't Believe It Can Sort 的排序算法,其伪代码简单到让人难以置信它真的能工作。该算法仅通过两层嵌套循环,反复比较并交换元素,直到数组有序。尽管时间复杂度为 O(n^2),效率远低于 quicksort 或 mergesort,但其逻辑之简洁令人称奇。文章展示了该算法的 Java 实现,并引用了相关研究论文,揭示了这一看似荒谬却真实有效的排序方法。

如果你看到伪代码,可能不会相信它真的能排序,但它确实可以。
  1. Someone

    关于该算法及其工作原理证明的论文:https://arxiv.org/pdf/2110.01111,其中写道:

    “这个算法毫无优点可言。它很慢——显然该算法在最坏、平均或最好情况下的运行时间都是 Θ(n2)。它不必要地比较了所有位置对两次(但见第 3 节)。它似乎缺乏直观理解,正确性也不完全显而易见。你肯定不想把它作为向学生介绍排序算法的第一个例子。它不稳定,不适合外部排序,无法处理在线到达的输入,也无法从部分有序的输入中获益。它唯一的吸引力可能在于其简洁性,体现在代码行数和两个循环的‘对称性’上。”

  2. petercooper

    说到有趣的小型排序算法,我一直觉得“睡眠排序(sleep sort)”挺逗:

    a=[5,3,1,4,2];b=[];a.map(n=>setTimeout(()=>b.push(n),n))

    显然现实中永远别用它,但我发现思考这个算法在不同语言中的行为和各种坑挺有意思的。

  3. senfiaj

    看起来像是次优的插入排序。

    第一次嵌套循环运行后,A[1] 将拥有最大值。

    第二次嵌套循环运行后,A[1] 总会与 A[2] 交换(除非它们相等,逻辑上不改变任何东西)。此时 A[2] 包含了最大值。

    在第 k 次(k >= 2)嵌套循环运行后,如果你仔细观察,第 k 个元素会被插入到前 k-1 个已排序元素中。当 j >= i 时,它就不再能做任何事情了,因为 A[k] 将包含最大值。

    在第 k 次(k >= 2)嵌套循环运行后,前 k 个元素将相对于彼此排序。第一次嵌套循环很特殊,它将最大元素带到了 A[1],随后的循环只是将 A[k] 从数组开头插入到前 k-1 个已排序元素中。

  4. fwlr

    它(直观上)不应该有效的理由有两个:一是内部 for 循环也是从头开始,而不检查外部 for 循环的位置,这意味着你会得到 `compare(a[0], a[2]) == true`,但同时也会得到 `compare(a[2], a[0]) == false`,所以看起来你无法从 `compare` 的结果中得出任何有意义的结论。另一个理由是符号方向反了。

    然而不知何故,这两个本应导致其失效的理由竟然以一种精确相互抵消的方式相互作用,从而产生了一个能工作的排序算法!

  5. edflsafoiewq

    之前(2021 年)的讨论:https://news.ycombinator.com/item?id=28758106

同日更多故事

2026-11-16