看起來滿是?bug?的排序代碼，居然是對的

↓推薦關(guān)注↓

轉(zhuǎn)自：量子位?公眾號（ QbitAI ）

程序 bug 也能負(fù)負(fù)得正嗎？

還真可以。

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

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

for?i?=?1?to?n?do
??for?j?=?1?to?n?do
????if?A[i]???????swap?A[i]?and?A[j]
最近這串代碼在 Hacker News 論壇上突然火了起來，引來大批程序員圍觀。

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

不等號方向錯了，第二層循環(huán)指數(shù) j 的范圍也弄錯了。

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

但如果你真的運行一下會發(fā)現(xiàn)，結(jié)果還真的是按照升序排列的。

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

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]，兩段程序大相徑庭。

然而我要告訴你一個不可思議的事實，其實第一串代碼是對的，而且可以嚴(yán)格證明。

那么它是如何實現(xiàn)正確排序的？

為何能歪打正著

仔細(xì)一想，其實很容易理解。因為該算法比冒泡排序多一半交換操作，正好可以將降序編程升序。

不過，作者還是給出了嚴(yán)格的證明。

我們定義 P? 是經(jīng)過 i 次（1 ≤ i ≤ n）外循環(huán)后得到的數(shù)組。

如果算法正確，那么前 i 項已經(jīng)是升序排列，即 A[1] ≤ A[2] ≤ . . . ≤ A[i]。

證明該算法正確，實際上就是證明 P? 對于任何 n 都成立。

根據(jù)數(shù)學(xué)歸納法，我們只要證明 P? 成立，假設(shè) P? 成立，接著再證明 Pi 1 也成立，命題即可得證。

P? 顯然是正確的，而且這一步和普通的冒泡算法降序沒有區(qū)別，經(jīng)過第 1 次外循環(huán)，A[1] 就是整個數(shù)組的最大元素。

接著我們假設(shè) P? 成立，然后證明 Pi 1 成立。

我們先定義一個序數(shù) k：

首先假設(shè) A[k](k 介于 1~i 之間）滿足 A[k]>A[i 1] 最小的一個數(shù)，那么 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]，沒有任何元素交換發(fā)生。

2、 k ≤ j ≤ i （如果 k=i 1，則不存在此步驟）

由于 A[j]>A[i 1]，所以每次比較后都會有元素交換發(fā)生。

我們使用 A[ ] 和 A′[ ] 來表示交換前和交換后的元素，所以

A′[i 1] = A[k]，A′[k]=A[i 1]

經(jīng)過一系列交換，最大元素最終被放到了 A[i 1] 位置上，原來的 A[i 1] 變成了最大元素，A[k] 被插入了大小介于原來 A[k] 和 A[k-1] 之間的元素。

3、i 1 ≤ j ≤ n

由于最大元素已經(jīng)交換到前 i 1 個元素中，此過程也沒有任何元素交換。

最后，P? 就是升序排序算法執(zhí)行完以后的結(jié)果。

由于內(nèi)外兩組循環(huán)沒有任何范圍差別，因此這可以說是“最簡單”的排序算法了。

從代碼上來看，它很像冒泡算法，但從證明過程中可以看出，這實際上是一種插入算法。

算法復(fù)雜度

顯然，該算法總會進行 n2 次比較，接下來計算算法的交換次數(shù)。

可以證明交換其次最多為 I 2(n-1)，最少為 n-1。

其中 I 為初始數(shù)字的逆序數(shù)，最大為 n(n-1)/2

因此整個算法的復(fù)雜度為 O(n2)。

從證明過程中可以看出，除了 i=1 的循環(huán)以外，其余循環(huán)里 j=i-1 之后的部分完全無效，因此可以將這部分省略，得到簡化后的算法。

for?i?=?2?to?n?do
??for?j?=?1?to?i???1?do
????if?A[i]?then
??????swap?A[i]?and?A[j]
該算法減少了比較和交換次數(shù)，不過算法復(fù)雜度依然是 O(n2)。

網(wǎng)友：這個算法我以前見過

比最容易理解的冒泡算法還要簡單，這個排序算法在 Hacker News 上很快引起了網(wǎng)友的圍觀。

不少人覺得它“很眼熟”。

有位網(wǎng)友表示，自己曾在奧林匹克數(shù)學(xué)競賽中看到一個同學(xué)用了一種非常奇怪的排序算法，它可以運行但是效率很低，更像是一種插入排序。

如果我沒記錯的話，他用的就是這種算法。

事實上，關(guān)于這種算法的討論已久，從 2014 年開始就不斷有人發(fā)帖，這次作者將論文上傳到 arXiv 后又引起了廣泛熱議。

甚至還有烏龍事件發(fā)生。

有位網(wǎng)友掃了一眼論文就以為這個算法和自己 10 年前提出的一樣。

留言網(wǎng)友的算法：

乍一看兩種算法的代碼確實很像，原理上的確有些相似。

都是看起來像冒泡排序，但其實更貼近選擇排序。

不過很快有人指出真相：這種算法中 j=i 1 to n，并且是當(dāng) A[i] > A[j] 時交換。

而作者提出的算法中 j=1 to n，A[i] < A[j] 時交換。

兩種算法相比，網(wǎng)友此前提出的更容易被理解為什么可以運行。

當(dāng)然也有歪樓的，有人就調(diào)侃自己剛學(xué)編程時寫過這個算法。

我百分百確定，在我剛開始學(xué)編程、并想要找到最短的排序方法時就寫過它。

不過說到實際應(yīng)用上，這種算法需要的計算時間太長了。

有人就認(rèn)為，這種算法此前被發(fā)現(xiàn)過很多次，但是那些人根本沒打算用它。

也有人提出：這種排序沒有睡眠排序簡單。

睡眠排序就是構(gòu)造 n 個線程，讓線程和排序的 n 個數(shù)對應(yīng)。

例如對于 [4,2,3,5,9] 這樣一組數(shù)字，就創(chuàng)建 5 個線程，每個線程睡眠 4s，2s，3s，5s，9s。這些線程睡醒之后，就把自己對應(yīng)的數(shù)報出來即可。這樣等所有線程都醒來，排序就結(jié)束了。

但和作者提出的算法一樣，睡眠排序由于多線程的問題，在真正實現(xiàn)上也有困難。

此外，這位網(wǎng)友也表示自己看到過這種算法：

我確定我此前看到過這種算法，它沒有名字嗎？

很快就有人提議說——

如果它沒有名字的話，我建議稱之為“面試排序”。

- EOF -