【算法】BOGO排序法

Richard

2018 年 12 月 26 日

1268 次浏览

暂无评论

789字数

数据结构与算法

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

起源

无限猴子定理

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

时间复杂度

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

意义

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

代码实现

#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啊(￣▽￣)

【算法】BOGO排序法