共计 2343 个字符，预计需要花费 6 分钟才能阅读完成。
明敏 晓查 发自 凹非寺 \
量子位 报道 | 公众号 QbitAI
程序 bug 也能负负得正吗？
还真能够。
比方程序员们再相熟不过的排序算法，通过两个“bug”竟然能歪打正着，切实令人匪夷所思。
请看这位程序员写的数组升序排序代码：
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]最近这串代码在 Hacker News 论坛上忽然火了起来，引来少量程序员围观。
乍一看这段代码，你的反馈会是什么？会不会感觉这个程序员程度太差了，连根本的 冒泡算法 都写不好：
不等号方向错了，第二层循环指数 j 的范畴也弄错了。
总之，这段代码“相对不可能正确”。
冒泡算法
但如果你真的运行一下会发现，后果还真的是依照升序排列的。
咱们再来看一下正确的冒泡算法代码是怎么的：
for i = 1 to n do
for j = i + 1 to n do
if A[i] > A[j] then
swap A[i] and A[j]后者不同之处是 j = i + 1 且 A[i] > A[j]，两段程序天壤之别。
然而我要通知你一个不堪设想的事实，其实第一串代码是对的，而且能够严格证实。
那么它是如何实现正确排序的？
为何能歪打正着
认真一想，其实很容易了解。因为该算法比冒泡排序多一半替换操作，正好能够将降序编程升序。
不过，作者还是给出了严格的证实。
咱们定义 Pᵢ 是通过 i 次（1 ≤ i ≤ n）外循环后失去的数组。
如果算法正确，那么前 i 项曾经是升序排列，即 A[1] ≤ A[2] ≤ . . . ≤ A[i]。
证实该算法正确，实际上就是证实 Pₙ 对于任何 n 都成立。
依据数学归纳法，咱们只有证实 P₁ 成立，假如 Pᵢ 成立，接着再证实 Pi+1 也成立，命题即可得证。
P₁ 显然是正确的，而且这一步和一般的冒泡算法降序没有区别，通过第 1 次外循环，A[1] 就是整个数组的最大元素。
接着咱们假如 Pᵢ 成立，而后证实 Pi+1 成立。
咱们先定义一个序数 k：
首先假如 Ak。
如果 A[i+1]≥A[i]，那么这样的 k 不存在，咱们就令 k=i+1。
思考以下三种状况：
1、1 ≤ j ≤ k−1
因为 A[i+1]>A[j]，没有任何元素替换产生。
2、k ≤ j ≤ i（如果 k=i+1，则不存在此步骤）
因为 A[j]>A[i+1]，所以每次比拟后都会有元素替换产生。
咱们应用 A[] 和 A′[] 来示意替换前和替换后的元素，所以
A′[i+1] = A[k]，A′[k]=A[i+1]通过一系列替换，最大元素最终被放到了 A[i+1] 地位上，原来的 A[i+1] 变成了最大元素，A[k] 被插入了大小介于原来 A[k] 和 A[k-1] 之间的元素。
3、i+1 ≤ j ≤ n
因为最大元素曾经替换到前 i+1 个元素中，此过程也没有任何元素替换。
最初，Pₙ 就是升序排序算法执行完当前的后果。
因为内外两组循环没有任何范畴差异，因而这能够说是“最简略”的排序算法了。
从代码上来看，它很像 冒泡算法 ，但从证实过程中能够看出，这实际上是一种 插入算法。
插入算法
算法复杂度
显然，该算法总会进行 n² 次比拟，接下来计算算法的替换次数。
能够证实替换其次最多为 I+2(n-1)，起码为 n-1。
其中 I 为初始数字的逆序数，最大为 n(n-1)/2
因而整个算法的复杂度为 O(n²)。
从证实过程中能够看出，除了 i=1 的循环以外，其余循环里 j=i-1 之后的局部齐全有效，因而能够将这部分省略，失去简化后的算法。
for i = 2 to n do
for j = 1 to i − 1 do
if A[i] < A[j] then
swap A[i] and A[j]该算法缩小了比拟和替换次数，不过算法复杂度仍然是 O(n²)。
网友：这个算法我以前见过
比最容易了解的冒泡算法还要简略，这个排序算法在 Hacker News 上很快引起了网友的围观。
不少人感觉它“很眼生”。
有位网友示意，本人曾在奥林匹克数学比赛中看到一个同学用了一种十分奇怪的排序算法，它能够运行然而效率很低，更像是一种插入排序。
如果我没记错的话，他用的就是这种算法。
事实上，对于这种算法的探讨已久，从 2014 年开始就一直有人发帖，这次作者将论文上传到 arXiv 后又引起了宽泛热议。
甚至还有乌龙事件产生。
有位网友扫了一眼论文就认为这个算法和本人 10 年前提出的一样。
留言网友的算法：
乍一看两种算法的代码的确很像，原理上确实有些类似。
都是看起来像冒泡排序，但其实更贴近抉择排序。
不过很快有人指出假相：这种算法中 j=i+1 to n，并且是当 A[i] > A[j] 时替换。
而作者提出的算法中 j=1 to n，A[i] < A[j] 时替换。
两种算法相比，网友此前提出的更容易被了解为什么能够运行。
当然也有歪楼的，有人就调侃本人刚学编程时写过这个算法。
我百分百确定，在我刚开始学编程、并想要找到最短的排序办法时就写过它。
不过说到理论利用上，这种算法须要的计算工夫太长了。
有人就认为，这种算法此前被发现过很屡次，然而那些人基本没打算用它。
也有人提出：这种排序没有 睡眠排序 简略。
睡眠排序就是结构 n 个线程，让线程和排序的 n 个数对应。
例如对于 [4,2,3,5,9] 这样一组数字，就创立 5 个线程，每个线程睡眠 4s，2s，3s，5s，9s。这些线程睡醒之后，就把本人对应的数报进去即可。这样等所有线程都醒来，排序就完结了。
但和作者提出的算法一样，睡眠排序因为多线程的问题，在真正实现上也有 艰难。
此外，这位网友也示意本人看到过这种算法：
我确定我此前看到过这种算法，它没有名字吗？
很快就有人提议说——
如果它没有名字的话，我倡议称之为“面试排序”。
近期热文举荐：
1.1,000+ 道 Java 面试题及答案整顿(2022 最新版)
2. 劲爆！Java 协程要来了。。。
3.Spring Boot 2.x 教程，太全了！
4. 别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！
