比冒泡算法還簡單的排序算法：看起來滿是bug的程序，居然是對的_風聞

　　明敏 曉查 發自 凹非寺

　　量子位 報道 | 公眾號 QbitAI

　　程序bug也能負負得正嗎？

　　還真可以。

　　比如程序員們再熟悉不過的排序算法，通過兩個“bug”居然能歪打正着，實在令人匪夷所思。

　　請看這位程序員寫的數組升序排序代碼：

　　for i = 1 to n dofor j = 1 to n doif A[i] < A[j] thenswap A[i] and A[j]

　　今天這串代碼在Hacker News論壇上突然火了起來，引來大批程序員圍觀。

　　乍一看這段代碼，你的反應會是什麼？會不會覺得這個程序員水平太差了，連基本的冒泡算法都寫不好：

　　不等號方向錯了，第二層循環指數j的範圍也弄錯了。

　　總之，這段代碼“絕對不可能正確”。

　　****△冒泡算法

　　但如果你真的運行一下會發現，結果還真的是按照升序排列的。

　　我們再來看一下正確的冒泡算法代碼是怎樣的：

　　for i = 1 to n dofor j = i + 1 to n doif A[i] > A[j] thenswap 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 dofor j = 1 to i − 1 doif A[i] < A[j] thenswap 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]https://news.ycombinator.com/item?id=28758106

　　[2]https://arxiv.org/abs/2110.01111