史上最簡(jiǎn)單排序算法？看起來卻滿是bug
今天在搜論文的時(shí)候，偶然發(fā)現(xiàn)一篇文章，名為<
算法
下面我看下偽代碼實(shí)現(xiàn)，在證明該排序算法正確性之前，我們暫且將其命名為ICan’tBelieveItCanSort??。
ICan’tBelieveItCanSort(A[1..n])?{
??for?i?=?1?to?n?do
????for?j?=?1?to?n?do
??????if?A[i]?then
????????swap(A[i],?A[j])
}
看了上面代碼的第一反應(yīng)是什么？會(huì)不會(huì)跟我一樣，覺得
?這不就是一個(gè)錯(cuò)誤的冒泡排序算法么，只是把第二行把范圍寫錯(cuò)，第三行交換的條件寫反了罷了??。
?
下面是冒泡排序的偽代碼：
BubbleSort(A[1..n])?{
??for?i?=?1?to?n?do
????for?j?=?i?+?1?to?n?do
??????if?(A[i]?>?A[j])?then
????????swap(A[i],?A[j]);
}
?為了后續(xù)描述方便，我將該算法統(tǒng)一稱之為"新算法"。
?
從上面兩個(gè)偽代碼的實(shí)現(xiàn)來看，新算法ICan’tBelieveItCanSort和傳統(tǒng)的冒泡排序算法BubbleSort的區(qū)別如下：
在新算法中，內(nèi)循環(huán)為 for j = 1 to n?
而在傳統(tǒng)的冒泡算法中，內(nèi)循環(huán)為 for j = i + 1 to n?
在新算法中，交換的條件為 if A[i] < A[j]
而在傳統(tǒng)的冒泡排序算法中，交換條件為 if A[i] > A[j]
好了，我們言歸正傳，重新轉(zhuǎn)回到新算法，為了方便大家閱讀，再此重新貼一次新算法的偽代碼：
ICan’tBelieveItCanSort(A[1..n])?{
??for?i?=?1?to?n?do
????for?j?=?1?to?n?do
??????if?A[i]?then
????????swap(A[i],?A[j])
}
先不論算法的正確與否，因?yàn)樵贏[i] < A[j]時(shí)候才進(jìn)行交換，所以上述代碼給我們的第一印象就是 按照降序排列。但實(shí)際上，通過代碼運(yùn)行結(jié)果來分析，其確實(shí)是升序排列。
下面給出證明過程。
證明
下面將通過數(shù)學(xué)歸納法來證明此算法的正確性。
假設(shè)P?是經(jīng)過 i 次（1 ≤ i ≤ n）外循環(huán)后得到的數(shù)組，那么前i項(xiàng)已經(jīng)是升序排列，即 A[1] ≤ A[2] ≤ . . . ≤ A[i]。
要證明該算法正確，只需要證明P對(duì)于任何[i + 1..n]都成立。
根據(jù)數(shù)學(xué)歸納法，我們只要證明 P?成立，假設(shè) P?成立，接著再證明 Pi+1 也成立，命題即可得證。
P?顯然是正確的，而且這一步和普通的冒泡算法降序沒有區(qū)別，經(jīng)過第1次外循環(huán)，A[1]就是整個(gè)數(shù)組的最大元素。
接著我們假設(shè)P?成立，然后證明 Pi+1 成立。
下面我們開始證明新算法的正確性??。
首先假設(shè)存在一個(gè)下標(biāo)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。
?
現(xiàn)在，我們考慮以下幾種情況：
1 ≤ j ≤ k?1 此時(shí)，由于A[1..i]是遞增有序，且A[K]是滿足A[k] > A[i+1] 最小的一個(gè)數(shù)，所以A[j] < A[i +1]，沒有任何元素交換發(fā)生。
k ≤ j ≤ i (顯然，當(dāng)k = i+1的時(shí)候，不會(huì)進(jìn)入此步驟)
由于 A[j] > A[i+1]，所以每次比較后都會(huì)有元素交換發(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]之間的元素。
i+1 ≤ j ≤ n
由于最大元素已經(jīng)交換到前 i+1 個(gè)元素中，此過程也沒有任何元素交換。
經(jīng)過上面一系列條件，最終，P就是升序排序算法執(zhí)行完以后的結(jié)果。
?由于內(nèi)外循環(huán)完全一樣，所以此算法可以說是最簡(jiǎn)單的排序算法了。
?
優(yōu)化
從上面的證明過程中，我們可以發(fā)現(xiàn)，除了 i=1 的循環(huán)以外，其余循環(huán)里 j=i-1 之后的部分完全無效，因此可以將這部分省略，得到簡(jiǎn)化后的算法。
ICan’tBelieveItCanSort(A[1..n])?{
??for?i?=?2?to?n?do
????for?j?=?1?to?i?-?1?do
??????if?A[i]?then
????????swap(A[i],?A[j])
}
對(duì)比
但從代碼來看，新算法像是冒泡算法的變種，但是從上面證明過程來看，新算法實(shí)際上是一種插入算法。
下面為新算法的模擬圖：
下面為冒泡算法的模擬圖：
實(shí)現(xiàn)
代碼實(shí)現(xiàn)比較簡(jiǎn)單，如下：
#include?
#include?
#include?
void?SimplestSort(std::vector?&v)?{
??for?(int?i?=?0;?i?????for?(int?j?=?0;?j???????if?(v[i]??std::swap(v[i],?v[j]);
??????}
????}
??}
}
int?main()?{
??std::vector?v?=?{9,?8,?1,?3,2,?5,?4,?7,?6};
??SimplestSort(v);
??for?(auto?item?:?v)?{
????std::cout?<??}
??return?0;
}
輸出結(jié)果：
1
2
3
4
5
6
7
8
9
更簡(jiǎn)單的算法？
看完這篇論文，突然想起之前有個(gè)更簡(jiǎn)單且容易理解的算法，我們暫且稱之為休眠算法。
思想：
?構(gòu)造n個(gè)線程，它們和這n個(gè)數(shù)一一對(duì)應(yīng)。初始化后，線程們開始睡眠，等到對(duì)應(yīng)的數(shù)那么多個(gè)時(shí)間單位后各自醒來，然后輸出它對(duì)應(yīng)的數(shù)。這樣最小的數(shù)對(duì)應(yīng)的線程最早醒來，這個(gè)數(shù)最早被輸出。等所有線程都醒來，排序就結(jié)束了。
?
例如對(duì)于 [4,2,3,5,9] 這樣一組數(shù)字，就創(chuàng)建 5 個(gè)線程，每個(gè)線程睡眠 4s，2s，3s，5s，9s。這些線程睡醒之后，就把自己對(duì)應(yīng)的數(shù)報(bào)出來即可。這樣等所有線程都醒來，排序就結(jié)束了。
算法思路很簡(jiǎn)單，但是存在一個(gè)問題，創(chuàng)建的線程數(shù)依賴于需要排序的數(shù)組的元素個(gè)數(shù)，因此這個(gè)算法暫且只能算是一個(gè)思路吧。
結(jié)語
這個(gè)算法不一定是史上最簡(jiǎn)單的排序算法，但卻是最神奇的排序算法。神奇之處在于 大于號(hào)和小于號(hào)顛倒了卻得到了正確的結(jié)果。
其實(shí)，我們完全可以用另外一個(gè)簡(jiǎn)單的思路來理解這個(gè)算法，那就是冒泡兩次，第一次非遞增排序，第二次非遞減排序，算是負(fù)負(fù)得正，得到了正確的結(jié)果吧。
由于"最簡(jiǎn)單"算法的時(shí)間復(fù)雜度過高，其僅僅算是一種實(shí)現(xiàn)思路，也算是開拓一下思路，實(shí)際使用的時(shí)候，還是建議使用 十大經(jīng)典排序算法。
今天的文章就到這里，下期見。
參考
https://arxiv.org/pdf/2110.01111v1.pdf
https://www.liangzl.com/