Bogo排序
外观
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
Bogo排序 | |
---|---|
概况 | |
類別 | 排序算法 |
資料結構 | 数组 |
复杂度 | |
平均時間複雜度 | [1] |
最坏时间复杂度 | ∞ |
最优时间复杂度 | |
空間複雜度 | |
最佳解 | No |
相关变量的定义 |
在计算机科学中,Bogo排序(bogo-sort)是個非常低效率的排序演算法,通常用在教學或測試。其原理等同將一堆卡片拋起,落在桌上後檢查卡片是否已整齊排列好,若非就再拋一次。其名字源自Quantum bogodynamics,又稱bozo sort、blort sort或猴子排序(參見無限猴子定理)。
实现
以下是偽代碼:
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 + 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個數*/
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;
}
运行时间
这个排序算法基于可能性。平均而言,让所有元素都被排好序的期望比较次数渐近于,期望的位置交换次数渐近。[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.
外部連結
- Jargon File上的條目(页面存档备份,存于互联网档案馆)
- Bogosort(页面存档备份,存于互联网档案馆): an implementation that runs on Unix-like systems, similar to the standard sort program.
- Bogosort: Simple C++ implementation of bogosort algorithm
|
|