猴子排序 详解（bushi）

userId_undefined
manbo
时间刺客空间掌握者时空双修者

2026-07-12 14:19:31

发布于：天津

22阅读
0回复
0点赞

猴子排序第1.11.1版

什么是猴子排序？

思想：

  • 每次把数组像猴子一样随机打乱（绷），判断其是否升序或降序；
  • 特别好理解，纯靠运气；
  • 运气好，比任何算法都快 ；运气不好，比苹果排序(也就是计数排序)、大饼排序、无聊排序还慢！

相关信息、复杂度：

  • 时间复杂度最好：O(1)O(1)（世界上最好的排序算法，但是靠运气）
  • 时间复杂度平均：O(n!)O(n!)
  • 时间复杂度最差：O(∞)O(∞)（6）
  • 空间复杂度 ：O(1)O(1)。原地排序（存操作序列不计）
  • 稳定性：不稳定（x78随机，相对位置改变）
  • other name：香蕉排序、洗牌排序。

参考代码

#include <cstdio>
#include <algorithm>
#include <ctime>
#include <random>
using namespace std;

// 判断升序有序（当然可以改成降序的）
// 可以背下来用
bool is_sorted(int a[], int n)
{
    for(int i = 0; i < n - 1; i++)
        if(a[i] > a[i + 1]) return false;
    return true;
}
void bogo_sort(int a[], int n)
{
    mt19937 rnd(time(0)); //可以搜搜这是什么内核...
    while(!is_sorted(a, n)){
        // 打乱.（python也是这个函数）
        shuffle(a, a + n, rnd);
    }
}
int main()
{
    int arr[] = {3, 1, 4, 1, 5, 2};
    int len = sizeof(arr) / sizeof(arr[0]);//这也可以背
    bogo_sort(arr, len);
    for(int i = 0; i < len; i++) printf("%d ", arr[i]);
    return 0;
}

10个数据belike：

搞笑。千万不要比赛时用!!!!!!!!!!!!!!!!!!!!!!!!!!!!

友情链接：
猴子排序📍你在此
大饼排序
无聊排序

userId_undefined
去预览
0/2000

全部评论 2

热门讨论