Bogo排序

在计算机科学中，Bogo排序（bogo-sort）是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序.

实现

以下是C代码：

 1 #include<stdio.h>    
 2 #include<string.h>   
 3 #include<math.h>   
 4 #include<ctype.h>   
 5 #include<stdbool.h>
 6 #include<stdlib.h>
 7 #include<time.h>
 8 
 9 void swap(int *a, int *b)   //交换两元素的值
10 {
11     int t;
12     t=*a;
13     *a=*b;
14     *b=t;
15 }
16 
17 void printArray(int a[], int count)   //打印数组元素
18 {
19     int i;
20     for(i=0; i<count; i++)
21         printf("%d ",a[i]);
22     printf("\n");
23 }
24 
25 unsigned int Random1(int a, int b)  //随机生成[a,b)之间的数
26 {
27     return (rand()%(b-a)+a);
28 }
29 
30 unsigned int Random2(int n)  //随机生成[0,n)之间的数
31 {
32     return (rand()%n);
33 }
34 
35 bool inorder(int a[], int n)  //判断序列是否已经有序
36 {
37     int i;
38     for(i=0; i<n; i++)
39     {
40         if(a[i] > a[i+1])  return false;
41     }
42     return true;
43 }
44 
45 void shuffle(int a[], int n)
46 {
47     int i,swapPosition;
48     for(i=0; i<n; i++)
49     {
50         swapPosition = Random2(i+1);
51         swap(&a[i],&a[swapPosition]);
52     }
53 }
54  
55 void bogo_sort(int a[], int n)
56 {
57     while(!inorder(a,n))
58         shuffle(a,n);
59 }
60 
61 int main(void)   
62 {
63     int a[]={3, 5, 4, 6, 9, 7, 8, 0, 1};
64     int n=sizeof(a)/sizeof(*a);
65     srand((unsigned)time(NULL));  
66     printArray(a,n);
67     bogo_sort(a,n);
68     printArray(a,n);    
69     return 0;
70 }

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

运行时间

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

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

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