明敏 曉查 發自 凹非寺 量子位 報道 | 公眾號 QbitAI 程式 bug 也能負負得正嗎？ 還真可以。 比如程式員們再熟悉不過的排序演算法，通過兩個“bug”居然能歪打正著，實在令人匪夷所思。 請看這位程式員寫的數組升序排序代碼： for i = 1 to n do for j = 1 to n ...
明敏 曉查 發自 凹非寺
量子位 報道 | 公眾號 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：
首先假設 A[k](k 介於 1~i 之間）滿足 A[k]>A[i+1] 最小的一個數，那麼 A[k−1]≤A[i+1]（k≠1)。
如果 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最新版)
4.別再寫滿屏的爆爆爆炸類了，試試裝飾器模式，這才是優雅的方式！！
覺得不錯，別忘了隨手點贊+轉發哦！
