前段時間，分享了《演算法導論》中的一些排序演算法，
最美排序：
《世界上最美的排序演算法！
時間復雜度為O(n)的三種排序：
《這個排序酷，O(n)
《這個排序靚，O(n)
《這個排序跩，O(n)
今天，和大家分享一個，世界上最慢的排序演算法，猴子排序（bogo sort），
話不多說，先上偽代碼：
int bogo_sort(int& arr[], int n){
while(false== is_sorted(arr[n])){
random_shuffle(arr[n]);
}
return 0;
}
之所以叫猴子排序，源自典故：一只猴子隨機敲擊鍵盤，只要時間足夠久，一定能敲出莎士比亞的詩，
看了偽代碼，很容易理解其核心思路是：
（1）判斷待排序的陣列是否有序，有序則回傳排序完畢；
（2）無序，則隨機打亂陣列；
（3）重復（1）；
只要執行的時間足夠長，隨機的次數足夠久，總能夠得到排序后的結果，它號稱是世界上最慢的排序演算法，
那么問題來了，這個排序有什么用呢？
我能夠想到的，就是大學里作為演算法課的時間復雜度推導習題，或者面試程序中時間復雜度計算考題了，又或者裝13的談資了，其他好像沒有什么用，
那這個排序演算法的時間復雜度是多少呢？
簡單來分析一下，
n個元素隨機打亂，有n!種組合，
一次排序成功的概率是p1 = 1/n!，一次排序失敗的概率是p2 = 1-p1；
兩次排序成功的概率是p2*p1；
畫外音：第1次失敗，第2次成功，
三次排序成功的概率是p2^2*p1；
畫外音：前2次失敗，第3次成功，
…
k次排序成功的概率是p2^(k-1)*p1
畫外音：前k-1次失敗，第k次成功，
…
于是，平均排序成功次數的期望：
E(X) =
1次 * 一次成功的概率
+
2次 * 二次成功的概率
+
3次 * 三次成功的概率
+
…
+
k次 * k次成功的概率
+
…
即：
最后，根據大家大學里學的無窮級數的數學知識，“很容易”得到，其時間復雜度是O(n*n!)，這是一個階乘級別的演算法，
架構師之路-分享可落地的技術文章
答應我，裝13可以，不要用這個考題去為難候選人，好么？謝謝大家！
調研：
你還見過更奇葩的排序演算法嗎？
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/333775.html
標籤：java