今天，和大家分享一個，世界上最慢的排序算法，猴子排序(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!)，這是一個階乘級別的算法。

【本文為51CTO專欄作者“58沈劍”原創稿件，轉載請聯系原作者】

戳這里，看該作者更多好文