bogobogo sort(doge)蠢猴排序

bogobogo sort(doge)蠢猴排序

众所周知,猴子排序是个非常看人品的排序,好的人一次完事,坏的人无限循环,谁都知道,打乱了再排,贴上代码

#include
using namespace std;
int a[10000],n;
bool sorted(int n)
{
  while (--n>=1) 
    if(a[n]

这是猴子排序,蠢猴排序是怎么运行的呢?比如:

一组平平无奇的样例

5 3 1 4 2

现在,有一个i指针指向下标为0的位置上(是5),5一个数是肯定排好序了

5 3 1 4 2

i指向的下标为1(是3)

接下来,把 5 3打乱,直到有序

3 5 1 4 2

i指向的下标为2(是1)

接下来,把 3 5 1打乱,直到有序

3 5 1 4 2

以此类推,直到全部有序

代码只要在bogo的基础上加一个for(int i=2;i<=n;i++)至于为什么从2开始,因为第一个数已经算是排好了(i代表到现在为止要排几个数)

贴上代码

#include
using namespace std;
int a[100001],n;
bool is_sorted(int n)
{
  while ( --n >= 1 ) 
    if (a[n]

时间复杂度(最好): O(n^2)
时间复杂度(最坏): O(∞)
时间复杂度(平均): O(n*n!^n)(doge)

注:不要用于打代码,不然程序要挂的(az)