Bogo排序
無效的排序算法,它會連續生成其輸入的排列,直到找到要排序的輸入
在电脑科学中,Bogo排序(英语:Bogosort)是个非常低效率的排序算法,通常用在教学或测试。其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自Quantum bogodynamics,又称bozo sort、blort sort或猴子排序(参见无限猴子定理)。
Bogo排序 | |
---|---|
概况 | |
类别 | 排序算法 |
数据结构 | 数组 |
复杂度 | |
平均时间复杂度 | [1] |
最坏时间复杂度 | |
最优时间复杂度 | |
空间复杂度 | |
最佳解 | No |
相关变量的定义 |
实现
编辑以下是伪代码:
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;
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");
}
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 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] 期望的位置交换次数增长地比期望比较次数快,是因为只需要比较几对元素就能发现元素是无序的,但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下,交换和比较次数都是无限的,这就像随机投掷硬币可能连续任意次正面向上。
最好的情况是所给的数据是已经排好序的,这种情况下不需要任何位置交换,而比较次数等于 。
对任何固定长度的数据,算法的预期运行时间像无限猴子定理一样是无限的:总有一些可能性让被正确排好序的序列出现。
相关算法
编辑Bozo排序
编辑Bozo排序是另一个基于随机数的算法。如果列表是无序的,就随机交换两个元素的位置再检查列表是否有序。
参见
编辑参考资料
编辑- ^ 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.