🐒猴子排序(优化版)

2026-08-07 22:20:04

发布于：江苏

98阅读

0回复

0点赞

——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥——防窥
原理：随机打乱数组，检查是否有序，无序就继续乱打乱，直到碰巧排好。
打个比方：让一只猴子乱敲键盘，敲出一篇完整的名著。
这只是趣味算法，完全不适合实际使用。n=50 几乎不可能跑出结果，时间复杂度最快为O(n)(运气极好，第一次打乱就直接有序)，否则就是O(n!)(直接爆炸💥)。

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <set>
#include <cstdio>

// Fisher‑Yates 标准洗牌 [start, end)
void fisherYatesShuffle(std::vector<int>& arr, size_t start, size_t end)
{
    for(size_t i = end - 1; i > start; --i)
    {
        size_t offset = rand() % (i - start + 1);
        size_t j = start + offset;
        std::swap(arr[i], arr[j]);
    }
}

/**
 * 极限优化猴子排序
 * 1.预生成target标准答案
 * 2.固定已经就位的前缀，不参与洗牌
 * 3.记忆去重：跳过已经出现过的排列，避免重复抽奖
 * 4.动态退避阈值，根据乱序区间长度自动调节
 * 5.次数上限保护
 */
bool bogoSortUltimate(std::vector<int>& arr, unsigned long long maxTry)
{
    size_t n = arr.size();
    if(n <= 1) return true;

    std::vector<int> target = arr;
    std::sort(target.begin(), target.end());
    if(arr == target) return true;

    std::set<std::vector<int>> seen; //记忆已经出现过的排列
    unsigned long long total = 0;
    unsigned long long localCnt = 0;
    unsigned long long backoffCnt = 0;
    unsigned int localFail = 0;

    while(arr != target)
    {
        if(total >= maxTry)
        {
            std::cout << "⚠️达到最大尝试次数，排序失败\n";
            std::cout << "总尝试:" << total << " 局部打乱:" << localCnt
                      << " 全局回退:" << backoffCnt
                      << " 已记忆不同排列数:" << seen.size() << "\n";
            return false;
        }

        //找到已经完全正确的前缀长度
        size_t fixedLen = 0;
        for(; fixedLen < n; fixedLen++)
        {
            if(arr[fixedLen] != target[fixedLen]) break;
        }
        size_t badLen = n - fixedLen; //剩余乱的部分长度

        //动态退避阈值：乱序片段越长，阈值越小，更容易触发全局洗牌
        unsigned int dynamicThreshold = static_cast<unsigned int>(6000 / (badLen > 0 ? badLen : 1));

        size_t shuffleStart;
        if(localFail > dynamicThreshold)
        {
            shuffleStart = 0;
            backoffCnt++;
            localFail = 0;
        }
        else
        {
            shuffleStart = (localFail > dynamicThreshold/2 && fixedLen>0) ? fixedLen-1 : fixedLen;
            localCnt++;
        }

        //洗牌，并且跳过曾经出现过的排列
        do
        {
            fisherYatesShuffle(arr, shuffleStart, n);
            total++;
        }while(seen.count(arr) && total < maxTry);

        seen.insert(arr);
        localFail++;
    }

    std::cout << "✅排序成功！总尝试次数:" << total << "\n";
    std::cout << "局部打乱:" << localCnt << " 全局回退:" << backoffCnt
              << " 一共出现不同排列:" << seen.size() << "\n";
    return true;
}

int main()
{
    srand((unsigned)time(NULL));

    std::vector<int> nums = {5, 2, 7, 1, 9, 3, 6};
    std::cout << "排序前：";
    for(int v : nums) std::cout << v << " ";
    std::cout << "\n";

    if(bogoSortUltimate(nums, 100000000ULL))
    {
        std::cout << "排序后：";
        for(int v : nums) std::cout << v << " ";
        std::cout << "\n";
    }
    return 0;
}