浅谈“猴子排序”

DeepSkyBlue__ · 2019-11-18 18:14:48 · 个人记录

注意：接下来所有内容皆为作者的扯淡，考试中万万不可用到！

好啦忽略上面那句话。

今天我们来讲一讲一种新型排序方法：猴子排序。

那什么是猴子排序呢？

看名字就知道，它是一种排序方法废话，只不过方法独特，思路新颖，思路和sort一样好理解，只不过还不是主流排序方法。

猴子排序的思路是什么呢？

猴子排序的概念由黄子feg于2019.11.11（哇）提出，通过随机化处理和循环，达到排序的效果。

上代码！

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    while(1)
    {
        bool flag=0;
        random_shuffle(a+1,a+n+1); 
        for(int i=1;i<n;i++)
            if(a[i]>a[i+1])flag=1; 
        if(!flag)break;
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    cout<<endl;
}//HZPX

random_shuffle 函数将数组随机打乱，接下来进行打标记判断，如果按顺序排列则退出循环，输出数组，否则继续循环。

怎么样是不是很简单很粗暴？

猴子排序的优点是什么呢？

它的代码简短，数据要求和快排类似，适合不知道冒泡排序的新手使用，缺点是对数据规模要求较高，规模过大会导致TLE。

这就是我关于猴子排序的介绍，若有不足之处还请及时指出！