Bogo排序 - 维基百科，自由的百科全书

Bogo排序
概况
類別	排序算法
資料結構	数组
复杂度
平均時間複雜度	${\displaystyle O(n\cdot n!)}$[1]
最坏时间复杂度	${\displaystyle O(\infty )}$
最优时间复杂度	${\displaystyle O(n)}$
空間複雜度	${\displaystyle O(n)}$
最佳解	No
相关变量的定义

在计算机科学中，Bogo排序（英語：Bogosort）是個非常低效率的排序演算法，通常用在教學或測試。其原理等同將一堆卡片拋起，落在桌上後檢查卡片是否已整齊排列好，若非就再拋一次。其名字源自Quantum bogodynamics，又稱bozo sort、blort sort或猴子排序（參見無限猴子定理）。

以下是偽代碼：

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

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

#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"); } 

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) 

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

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

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

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

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

• 暴力搜尋法

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