查看“︁Bogo排序”︁的源代码

{{NoteTA
|G1 = IT
}}
{{算法信息框
| image = 
| class = [[排序算法]]
| data = [[数组]]
| time = <math>O(\infin)</math>
| average-time = <math>O(n\cdot n!)</math><ref name="Fun07 " />
| best-time = <math>O(n)</math>
| space = <math>O(n)</math>
| Def1 = 
| optimal = No
}}
在[[计算机科学]]中，'''Bogo排序'''（{{lang-en|Bogosort}}）是個非常低效率的[[排序演算法]]，通常用在教學或測試。其原理等同將一堆卡片拋起，落在桌上後檢查卡片是否已整齊排列好，若非就再拋一次。其名字源自"bogus"，又稱bozo sort、blort sort或猴子排序（參見[[無限猴子定理]]）。

== 实现 ==

以下是偽代碼：

<syntaxhighlight>
 function bogosort(arr)
   while arr is not ordered
       arr := 隨機排列(arr)
</syntaxhighlight>

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

=== C ===
<syntaxhighlight lang="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;
    for(i=total_elem-1;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個數 */
        /* 也等同於從搖獎機或籤筒裡抽出2個數x跟y並交換l[x]與l[y]（Bozo排序） */
        shuffle(l,sizeof(l[0]),n);
        isSort=1;
        /* 檢查從搖獎機或籤筒裡所抽出來的數是否比前一個數還大 */
        for(i=0;i<n-1;i++){
            if(l[i]>l[i+1]){ /* 若較大的陣列編號的值比較小時則重新洗牌 */
                isSort=0;
                break;
            }
        }
    }
    for(i=0;i<n;i++){
        printf("%d ",l[i]);
    }
    printf("\n");
}
</syntaxhighlight>

=== Python ===
<syntaxhighlight lang="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)        
</syntaxhighlight>

=== Java ===
<syntaxhighlight lang="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;
}
</syntaxhighlight>


===[[Julia (程式語言)]]===
<syntaxhighlight lang="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
</syntaxhighlight>

== 运行时间 ==
这个[[排序算法]]基于[[可能性]]。平均而言，让所有元素都被排好序的期望比较次数[[渐近]]于<math>(e-1) n!</math>，期望的位置交换次数渐近<math>(n-1) n!</math>。<ref name="Fun07">H. Gruber, M. Holzer and O. Ruepp: ''[http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms] {{Wayback|url=http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf |date=20110719055819 }}'', 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.</ref> 期望的位置交换次数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。

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

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

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

== 參見 ==
* [[暴力搜尋法]]

== 参考资料 ==
<references/>

== 外部連結 ==
* [http://www.catb.org/~esr/jargon/html/B/bogo-sort.html Jargon File上的條目]{{Wayback|url=http://www.catb.org/~esr/jargon/html/B/bogo-sort.html |date=20051223091209 }}
* [http://www.lysator.liu.se/~qha/bogosort/ Bogosort]{{Wayback|url=http://www.lysator.liu.se/~qha/bogosort/ |date=20090819233027 }}: an implementation that runs on [[Unix-like]] systems, similar to the standard [[sort (Unix)|sort]] program.
* [https://archive.today/20130103015524/http://github.com/versesane/algorithms-and-data-structures-in-c/tree/master/bogosort.c Bogosort]: Simple C++ implementation of bogosort algorithm

{{排序算法表}}
{{算法}}
[[Category:排序算法]]