Bogo排序

维基百科,自由的百科全书
跳转至: 导航搜索
Bogo排序
分類 排序算法
數據結構 数组
最差時間複雜度
最優時間複雜度 O(n)
平均時間複雜度 O(n\cdot n!)
最差空間複雜度 O(n)

计算机科学中,Bogo排序(bogo-sort)是個既不實用又原始的排序演算法,其原理等同將一堆卡片拋起,落在桌上後檢查卡片是否已整齊排列好,若非就再拋一次。其名字源自Quantum bogodynamics,又稱bozo sort、blort sort或猴子排序(參見無限猴子定理)。

实现[编辑]

以下是偽代碼:

函數 bogosort(陣列)
   當 非 有序(陣列)
      陣列 := 隨機排列(陣列)

其平均時間複雜度是 O(n × n!),在最壞情況所需時間是無限。它並非一個穩定的算法。

Python[编辑]

from random import shuffle
from itertools import izip, tee
 
def in_order(my_list):
    """Check if my_list is ordered"""
    it1, it2 = tee(my_list)
    it2.next()
    return all(a<=b for a,b in izip(it1, it2))
 
def bogo_sort(my_list):
    """Bogo-sorts my_list in place."""
    while not in_order(my_list):
        shuffle(my_list)

Java[编辑]

Random random = new Random();
 
public void bogoSort(int[] n) {
    while(!inOrder(n))shuffle(n);
}
 
public void shuffle(int[] n) {
    for (int i = 0; i < n.length; i++) {
        int swapPosition = random.nextInt(i + 1);
        int temp = n[i];
        n[i] = n[swapPosition];
        n[swapPosition] = temp;
    }
}
 
public boolean inOrder(int[] n) {
    for (int i = 0; i < n.length-1; i++) {
        if (n[i] > n[i+1]) return false;
    }
    return true;
}

运行时间[编辑]

这个排序算法基于可能性。平均而言,让所有元素都被排好序的期望比较次数渐近(e-1) n!,期望的位置交换次数渐近(n-1) n![1] 期望的位置交换次数增长地比期望比较次数快,是因为只需要比较几对元素就能发现元素是无序的,但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下,交换和比较次数都是无限的,这就像随机投掷硬币可能连续任意次正面向上。

最好的情况是所给的数据是已经排好序的,这种情况下不需要任何位置交换,而比较次数等于n-1

对任何固定长度的数据,算法的预期运行时间像无限猴子定理一样是无限的:总有一些可能性让被正确排好序的序列出现。

相关算法[编辑]

Bozo排序[编辑]

Bozo排序是另一个基于随机数的算法。如果列表是无序的,就随机交换两个元素的位置再检查列表是否有序。

量子Bogo排序[编辑]

计算机科学家之间的一个笑话说:量子计算机能够以 O(n) 的复杂度更有效地实现Bogo排序。这将使用真正的量子的随机性来随机打乱列表。根据量子物理学的多世界诠释,量子的随机性分别在无限的宇宙序列中展开,其中的一些将会提供一个排好序的列表。因为需要重新排列的次数虽然很大但仍然是有限的。这个列表接着就被测试出来(需要n-1次比较)。接着,计算机就应该实施“摧毁宇宙”的操作,使得在剩下的宇宙中的观察者能够得到一个排好序的列表。

參見[编辑]

参考资料[编辑]

  1. ^ H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.

外部連結[编辑]