Bogo排序(Bogo Sort)演算法又稱為猴子排序(Monkey Sort)演算法,顧名思義,是非常愚蠢的排序演算法,就像是請猴子幫忙排序一樣。



Bogo排序法(Bogo Sort)

Bogo排序法的概念

Bogo排序法十分簡單,一開始先檢查序列是否已經排序完成,如果沒有的話就不斷地隨機弄亂它的元素順序,直到剛好完成排序為止。

Bogo排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

由於它還不是一個已遞增排列好的陣列,所以要將它的元素順序隨機弄亂。弄亂之後的結果可能如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   79  38  81   2  30  47   9  69  32  61

因為還沒排序完成,所以繼續隨機弄亂。弄亂之後的結果可能如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   38  81   2  30  79  61  47   9  32  69

此時也還是沒有排序完成,所以繼續隨機弄亂。重覆進行上述動作之後,總會有一次可以恰好弄亂成已排序好的序列。

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

Bogo排序法的程式實作

Bogo排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(\infty)}}#隨機亂排總是不巧地都沒猜中。
最佳時間複雜度#{{O(n)}}#排序已經正向排序過的序列。
平均時間複雜度#{{O({n \times n!})}}#隨機亂排猜中的機率為#{{n!}}#,再乘上每次亂排前檢查是否已排序的時間複雜度。
額外最差空間複雜度#{{O(1)}}#
是否穩定