Bogo排序

Bogo排序
概况
类别	排序算法
数据结构	数组
复杂度
平均时间复杂度
最坏时间复杂度	∞
最优时间复杂度
空间复杂度
最佳解	No
相关变量的定义

在计算机科学中，Bogo排序（bogo-sort）是个非常低效率的排序算法，通常用在教学或测试。其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。

实现

以下是伪代码：

 function bogosort(arr)
   while arr is not ordered
       arr := 隨機排列(arr)

其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。

C

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 

void swap(void *a, void *b) {
    unsigned char *p = a;
    unsigned char *q = b;
    unsigned char tmp;
    tmp = *p;        
    *p = *q;         
    *q = tmp;        
}
/*洗牌函數*/
void shuffle(void *x, int size_elem, int total_elem) {
    int i = total_elem - 1;             
    for(i ; i >= 0; --i) {
        int r = rand() % (i+1);
        swap(x + r*size_elem, x + i*size_elem);
    }                 
}

int main(int argc, char *argv[]) {
    /*為了洗牌而需要隨機化函數，此處的函數具有偽隨機性*/
    srand((unsigned)time(NULL));
    int l[] = {5,2,1,3,4};
    int n;
    n = sizeof(l)/sizeof(l[0]);
    /*先設陣列未排序=0,已排序=1*/
    int isSort = 0;
    int i;
    while(!isSort) {
        /*進行洗牌動作*/
        /*等同於從搖獎機或籤筒裡依序抽出n個數*/
        shuffle(l, sizeof(l[0]), n);
        isSort = 1;
        /*檢查從搖獎機或籤筒裡所抽出來的數是否比前一個數還大*/
        for(i = 0; i < n-1; i++) {
            if (l[i] > l[i+1]) {/*若較大的陣列編號的值比較小時則重新洗牌*/
                isSort = 0;
                break;
            }
        }
    }
}

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;
}

Julia (编程语言)

# Julia Sample : BogoSort

function inOrder(A)
	for i=1:length(A)-1
		if A[i]>A[i+1]
			return false
		end
	end
	return true
end

function BogoSort(A)
	while (!inOrder(A))
		# Shuffle
		for i=1:length(A)
			r = rand(1:length(A))
			A[i],A[r]=A[r],A[i]
		end
	end
	return A
end

# Main Code
A = [16,586,1,31,354,43,3]
println(A)               # Original Array
println(BogoSort2(A))     # Bogo Sort Array

运行时间

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

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

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

参见

暴力搜索法

参考资料

^ ^1.0 ^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.

外部链接

Jargon File上的条目（页面存档备份，存于互联网档案馆）
Bogosort（页面存档备份，存于互联网档案馆）: an implementation that runs on Unix-like systems, similar to the standard sort program.
Bogosort: Simple C++ implementation of bogosort algorithm

[Fun07-1] 1.0 ^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.

[1]