在计算机科学中，Bogo排序（bogo-sort）是个非常低效率的排序算法，通常用在教学或测试。其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。
目录 1 实现 1.1 C 1.2 Python 1.3 Java 1.4 Julia (编程语言) 2 运行时间 3 相关算法 3.1 Bozo排序 4 参见 5 参考资料 6 外部链接 实现 以下是伪代码：
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 + rsize_elem, x + isize_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 运行时间 这个排序算法基于可能性。平均而言，让所有元素都被排好序的期望比较次数渐近于 ( � − 1 ) � ! (e-1)n!，期望的位置交换次数渐近 ( � − 1 ) � ! (n-1)n!。[1] 期望的位置交换次数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。
最好的情况是所给的数据是已经排好序的，这种情况下不需要任何位置交换，而比较次数等于 � − 1 n-1。
对任何固定长度的数据，算法的预期运行时间像无限猴子定理一样是无限的：总有一些可能性让被正确排好序的序列出现。
相关算法 Bozo排序 Bozo排序是另一个基于随机数的算法。如果列表是无序的，就随机交换两个元素的位置再检查列表是否有序。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: