看起來(lái)滿是bug的程序，居然是對(duì)的？比冒泡算法還簡(jiǎn)單的排序算法
時(shí)間：2021-10-22 15:20:53
手機(jī)看文章
掃描二維碼
隨時(shí)隨地手機(jī)看文章
[導(dǎo)讀]關(guān)注星標(biāo)公眾號(hào)，不錯(cuò)過(guò)精彩內(nèi)容來(lái)源|量子位程序bug也能負(fù)負(fù)得正嗎？世界之大，無(wú)奇不有，還真可以。比如程序員們?cè)偈煜げ贿^(guò)的排序算法，通過(guò)兩個(gè)“bug”居然能歪打正著，實(shí)在令人匪夷所思。請(qǐng)看這位程序員寫(xiě)的數(shù)組升序排序代碼：fori=1tondoforj=1tondoifA[i]
關(guān)注 星標(biāo)公眾號(hào)，不錯(cuò)過(guò)精彩內(nèi)容
for i = 1 to n dofor j = 1 to n doif A[i] < A[j] thenswap A[i] and A[j] 今天這串代碼在Hacker News論壇上突然火了起來(lái)，引來(lái)大批程序員圍觀。
乍一看這段代碼，你的反應(yīng)會(huì)是什么？會(huì)不會(huì)覺(jué)得這個(gè)程序員水平太差了，連基本的冒泡算法都寫(xiě)不好：
不等號(hào)方向錯(cuò)了，第二層循環(huán)指數(shù)j的范圍也弄錯(cuò)了。
總之，這段代碼“絕對(duì)不可能正確”。
△冒泡算法
但如果你真的運(yùn)行一下會(huì)發(fā)現(xiàn)，結(jié)果還真的是按照升序排列的。
我們?cè)賮?lái)看一下正確的冒泡算法代碼是怎樣的：
-
-
-
-
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] ，兩段程序大相徑庭。
然而我要告訴你一個(gè)不可思議的事實(shí)，其實(shí)第一串代碼是對(duì)的，而且可以嚴(yán)格證明。
那么它是如何實(shí)現(xiàn)正確排序的？
為何能歪打正著
仔細(xì)一想，其實(shí)很容易理解。因?yàn)樵撍惴ū让芭菖判蚨嘁话虢粨Q操作，正好可以將降序編程升序。
不過(guò)，作者還是給出了嚴(yán)格的證明。
我們定義P?是經(jīng)過(guò)i次（1 ≤ i ≤ n）外循環(huán)后得到的數(shù)組。
如果算法正確，那么前i項(xiàng)已經(jīng)是升序排列，即A[1] ≤ A[2] ≤ . . . ≤ A[i]。
證明該算法正確，實(shí)際上就是證明P?對(duì)于任何n都成立。
根據(jù)數(shù)學(xué)歸納法，我們只要證明P?成立，假設(shè)P?成立，接著再證明Pi 1也成立，命題即可得證。
P?顯然是正確的，而且這一步和普通的冒泡算法降序沒(méi)有區(qū)別，經(jīng)過(guò)第1次外循環(huán)，A[1]就是整個(gè)數(shù)組的最大元素。
接著我們假設(shè)P?成立，然后證明Pi 1成立。
我們先定義一個(gè)序數(shù)k：
首先假設(shè)A[k]（k介于1~i之間）滿足A[k]>A[i 1]最小的一個(gè)數(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]，沒(méi)有任何元素交換發(fā)生。
2、 k ≤ j ≤ i （如果k=i 1，則不存在此步驟）
由于A[j]>A[i 1]，所以每次比較后都會(huì)有元素交換發(fā)生。
我們使用A[ ]和A′[ ]來(lái)表示交換前和交換后的元素，所以
A′[i 1] = A[k]，A′[k]=A[i 1]
經(jīng)過(guò)一系列交換，最大元素最終被放到了A[i 1] 位置上，原來(lái)的A[i 1]變成了最大元素，A[k]被插入了大小介于原來(lái)A[k]和A[k-1]之間的元素。
3、i 1 ≤ j ≤ n
由于最大元素已經(jīng)交換到前i 1個(gè)元素中，此過(guò)程也沒(méi)有任何元素交換。
最后，P?就是升序排序算法執(zhí)行完以后的結(jié)果。
由于內(nèi)外兩組循環(huán)沒(méi)有任何范圍差別，因此這可以說(shuō)是“最簡(jiǎn)單”的排序算法了。
從代碼上來(lái)看，它很像冒泡算法，但從證明過(guò)程中可以看出，這實(shí)際上是一種插入算法。
△插入算法
算法復(fù)雜度
顯然，該算法總會(huì)進(jìn)行n2次比較，接下來(lái)計(jì)算算法的交換次數(shù)。
可以證明交換其次最多為I 2(n-1)，最少為n-1。
其中I為初始數(shù)字的逆序數(shù)，最大為n(n-1)/2
因此整個(gè)算法的復(fù)雜度為O(n2)。
從證明過(guò)程中可以看出，除了i=1的循環(huán)以外，其余循環(huán)里j=i-1之后的部分完全無(wú)效，因此可以將這部分省略，得到簡(jiǎn)化后的算法。
-
-
-
-
for i = 2 to n dofor j = 1 to i ? 1 doif A[i] < A[j] thenswap A[i] and A[j] 該算法減少了比較和交換次數(shù)，不過(guò)算法復(fù)雜度依然是O(n2)。
網(wǎng)友：這個(gè)算法我以前見(jiàn)過(guò)
比最容易理解的冒泡算法還要簡(jiǎn)單，這個(gè)排序算法在Hacker News上很快引起了網(wǎng)友的圍觀。
不少人覺(jué)得它“很眼熟”。
有位網(wǎng)友表示，自己曾在奧林匹克數(shù)學(xué)競(jìng)賽中看到一個(gè)同學(xué)用了一種非常奇怪的排序算法，它可以運(yùn)行但是效率很低，更像是一種插入排序。
如果我沒(méi)記錯(cuò)的話，他用的就是這種算法。
事實(shí)上，關(guān)于這種算法的討論已久，從2014年開(kāi)始就不斷有人發(fā)帖，這次作者將論文上傳到arXiv后又引起了廣泛熱議。
甚至還有烏龍事件發(fā)生。
有位網(wǎng)友掃了一眼論文就以為這個(gè)算法和自己10年前提出的一樣。
留言網(wǎng)友的算法：
乍一看兩種算法的代碼確實(shí)很像，原理上的確有些相似。
都是看起來(lái)像冒泡排序，但其實(shí)更貼近選擇排序。
不過(guò)很快有人指出真相：這種算法中 j=i 1 to n，并且是當(dāng) A[i] > A[j] 時(shí)交換。
而作者提出的算法中 j=1 to n，A[i] < A[j] 時(shí)交換。
兩種算法相比，網(wǎng)友此前提出的更容易被理解為什么可以運(yùn)行。
當(dāng)然也有歪樓的，有人就調(diào)侃自己剛學(xué)編程時(shí)寫(xiě)過(guò)這個(gè)算法。
我百分百確定，在我剛開(kāi)始學(xué)編程、并想要找到最短的排序方法時(shí)就寫(xiě)過(guò)它。
不過(guò)說(shuō)到實(shí)際應(yīng)用上，這種算法需要的計(jì)算時(shí)間太長(zhǎng)了。
有人就認(rèn)為，這種算法此前被發(fā)現(xiàn)過(guò)很多次，但是那些人根本沒(méi)打算用它。
也有人提出：這種排序沒(méi)有睡眠排序簡(jiǎn)單。
睡眠排序就是構(gòu)造n個(gè)線程，讓線程和排序的n個(gè)數(shù)對(duì)應(yīng)。
例如對(duì)于[4,2,3,5,9]這樣一組數(shù)字，就創(chuàng)建5個(gè)線程，每個(gè)線程睡眠4s，2s，3s，5s，9s。這些線程睡醒之后，就把自己對(duì)應(yīng)的數(shù)報(bào)出來(lái)即可。這樣等所有線程都醒來(lái)，排序就結(jié)束了。
但和作者提出的算法一樣，睡眠排序由于多線程的問(wèn)題，在真正實(shí)現(xiàn)上也有困難。
此外，這位網(wǎng)友也表示自己看到過(guò)這種算法：
我確定我此前看到過(guò)這種算法，它沒(méi)有名字嗎？
很快就有人提議說(shuō)——
如果它沒(méi)有名字的話，我建議稱(chēng)之為“面試排序”。
參考鏈接：
[1]https://news.ycombinator.com/item?id=28758106
[2]https://arxiv.org/abs/2110.01111
聲明：本文素材來(lái)源網(wǎng)絡(luò)，版權(quán)歸原作者所有。如涉及作品版權(quán)問(wèn)題，請(qǐng)與我聯(lián)系刪除。
------------ END ------------
●嵌入式專(zhuān)欄精選教程●精選匯總 | ST工具、下載編程工具●精選匯總 | 嵌入式軟件設(shè)計(jì)與開(kāi)發(fā)●精選匯總 | STM32、MCU、單片機(jī)
歡迎關(guān)注我的公眾號(hào)，回復(fù)“加群”按規(guī)則加入技術(shù)交流群，回復(fù)“1024”查看更多內(nèi)容。
歡迎關(guān)注我的視頻號(hào)：
點(diǎn)擊“閱讀原文”查看更多分享，歡迎點(diǎn)分享、收藏、點(diǎn)贊、在看。
下載文檔
