長見識(shí)了！世界上最慢的排序算法！
作者：58沈劍
今天，和大家分享一個(gè)，世界上最慢的排序算法，猴子排序。之所以叫猴子排序，源自典故：一只猴子隨機(jī)敲擊鍵盤，只要時(shí)間足夠久，一定能敲出莎士比亞的詩。
今天，和大家分享一個(gè)，世界上最慢的排序算法，猴子排序(bogo sort)。
話不多說，先上偽代碼：
- int bogo_sort(int& arr[], int n){
- while(false== is_sorted(arr[n])){
- random_shuffle(arr[n]);
- }
- return 0;
- }
之所以叫猴子排序，源自典故：一只猴子隨機(jī)敲擊鍵盤，只要時(shí)間足夠久，一定能敲出莎士比亞的詩。
看了偽代碼，很容易理解其核心思路是：
(1)判斷待排序的數(shù)組是否有序，有序則返回排序完畢;
(2)無序，則隨機(jī)打亂數(shù)組;
(3)重復(fù)(1);
只要執(zhí)行的時(shí)間足夠長，隨機(jī)的次數(shù)足夠久，總能夠得到排序后的結(jié)果，它號(hào)稱是世界上最慢的排序算法。
那么問題來了，這個(gè)排序有什么用呢?
我能夠想到的，就是大學(xué)里作為算法課的時(shí)間復(fù)雜度推導(dǎo)習(xí)題，或者面試過程中時(shí)間復(fù)雜度計(jì)算考題了，又或者裝13的談資了，其他好像沒有什么用。
那這個(gè)排序算法的時(shí)間復(fù)雜度是多少呢?
簡單來分析一下。
n個(gè)元素隨機(jī)打亂，有n!種組合。
- 一次排序成功的概率是p1 = 1/n!，一次排序失敗的概率是p2 = 1-p1;
- 兩次排序成功的概率是p2*p1;畫外音：第1次失敗，第2次成功。
- 三次排序成功的概率是p2^2*p1;畫外音：前2次失敗，第3次成功。
- …
- k次排序成功的概率是p2^(k-1)*p1畫外音：前k-1次失敗，第k次成功。
- …
于是，平均排序成功次數(shù)的期望：
E(X) =1次 * 一次成功的概率+2次 * 二次成功的概率+3次 * 三次成功的概率+…+k次 * k次成功的概率+…
即：
最后，根據(jù)大家大學(xué)里學(xué)的無窮級(jí)數(shù)的數(shù)學(xué)知識(shí)，“很容易”得到，其時(shí)間復(fù)雜度是O(n*n!)，這是一個(gè)階乘級(jí)別的算法。
【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
責(zé)任編輯：趙寧寧
來源：
51CTO專欄
