Bogo排序

Bogo排序是一種基於生成和測試範例的高效無效的排序功能。 該函式連續生成其輸入的排列，直到找到排序的排列。 它對於排序沒有用，但可以用於教育目的，以將其與更有效的算法進行對比。 存在兩個版本的函式：一個為確定性版本，它枚舉所有排列直到它遇到一個排序的，和一個隨機排列其輸入的隨機版本。 後一版本的工作類比是通過將甲板扔到空中，隨機挑選卡片並重複該過程直到甲板被分類來對一副紙牌進行分類。 它的名字來自偽造一詞.

功能說明

以下是偽代碼中隨機函式的描述：

以下是在Python 3中重寫的上述偽代碼：

當然，這假設數據是一個簡單的，可變的數據類型 - 就像Python的內置列表 - 其元素可以毫無問題地進行比較。

以下是標準ML中帶有shuffle的代碼示例：

運行時間和終止

如果要排序的所有元素都是不同的   ，那么通過隨機化bogosort在平均情況下執行的預期比較次數漸近等效於（e-1）n！ ，平均情況下預期的掉期數等於（n-1）n！預期的交換數量比預期的比較數量增長得快，因為如果元素不按順序排列，通常只需要進行幾次比較就可以發現，無論有多少元素;但洗牌的工作與其規模成正比。在最壞的情況下，比較和交換的數量都是無界限的，原因與拋擲的硬幣可能連續多次翻起頭部的原因相同。

如果給定的列表已經排序，則會出現最好的情況;在這種情況下，預期的比較次數是n-1，並且根本不進行交換。

對於任何固定大小的集合，算法的預期運行時間是有限的，這與無限猴子定理所持有的原因大致相同：有一些獲得正確置換的機率，所以給定無限次數的嘗試，它幾乎肯定會最終被選中。

相關算法

1、Gorosort

2、Bogobogosort

3、Bozosort

4、Worstsort

運行時間分析

這裡有一些Python代碼可以有效地測試Bogosort的平均複雜度。