【算法】BOGO排序法

Richard

2018 年 12 月 26 日

1358 次浏览

暂无评论

789字数

数据结构与算法

------------

- 今日闲来无事，突发奇想想写一些特别的东西，然后就想到了这个排序方法：BOGO排序法（又名猴子排序法）。

##起源
#####无限猴子定理
表述如下：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字，比如莎士比亚的全套著作。

##时间复杂度
平均时间复杂度是 O(n × n!)，欧皇是O(1),而非酋是无限。

##意义
这个算法突破了基于比较的排序算法最优时间复杂度只能是O(NlogN)的限制（手动滑稽）

##代码实现
```cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <ctime> 
using namespace std;

typedef vector<int> V;
typedef vector<int>::iterator VI;

void swap(VI a, VI b)//交换两个数
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void shuffle(VI x, int total_elem)//输入迭代器和元素个数
{
	int i = total_elem - 1;

for (i; i >= 0; --i) 
	{
		int r = rand() % (i + 1);//随机交换位置
		swap(x + r, x + i);
	}
}

int main(int argc, char *argv[]) 
{
	time_t start, end;//计时用的
	srand((unsigned)time(NULL)); //播种子

int n;
	
	cout << "你想输入几个整数？";
	cin >> n;
	cout << "那就输入" << n << "个整数吧" << endl;

V l(n);

for (int i = 0; i < n; i++)
		cin >> l[i];

start = time(NULL);

bool isSort = false;

while (!isSort) 
	{
		VI it = l.begin();

shuffle(it, n);
		isSort = true;
		for (int i = 0; i < n - 1; i++) 
		{
			if (l[i] > l[i + 1]) 
			{
				isSort = false;
				break;
			}
		}
	}

end = time(NULL);

cout << "排序用了：" << end - start << "秒" << endl;
	cout << "排序结果是：";

for (int i = 0; i < n; i++)
		cout << l[i] << " ";

cout << endl;
	
	system("pause");

return 0;
}
```

##作用
测试你的非酋程度（滑稽）
装 ~~.哔.~~ 
有人讨论是用快排好，还是堆排或者其他神奇的排序方法那个更好的时候，你可以吊吊的说：
“你们这群菜 ，我给你们写一个O（1）的算法吧～”（误）

##引申
#####量子Bogo排序
计算机科学家之间的一个笑话说：量子计算机能够以 O(n) 的复杂度更有效地实现Bogo排序。这将使用真正的量子的随机性来随机打乱列表。根据量子物理学的多世界诠释，量子的随机性分别在无限的宇宙序列中展开，其中的一些将会提供一个排好序的列表。这个列表接着就被测试出来（需要[ i ]n-1次比较），如果顺序不对，这个宇宙就被毁灭掉。因此最后只剩下得出正确顺序的宇宙。

这是我吃饱了撑着整的东西，别真拿去写OJ啊(￣▽￣)

最后修改：2019 年 04 月 13 日