猴子排序(点个赞吧，求求了）

珠江新城-张老师
2026-10-06 15:20:32
发布于：广东
11阅读
0回复
0点赞
不要放DEV,放ACgo
#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::shuffle
#include <random>    // 用于现代随机数生成
#include <chrono>    // 用于计时（可选，增加趣味性）

// 检查数组是否已按升序排列
bool isSorted(const std::vector<int>& arr) {
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

// 猴子排序主逻辑
bool bogoSort(std::vector<int>& arr) {
    // 初始化随机数生成器
    std::random_device rd;
    std::mt19937 gen(rd());
    
    long long attempts = 0;
    // 设置最大尝试次数，防止无限循环导致程序卡死
    // 对于 n=10，n! = 3,628,800，设置稍大一点的值作为安全网
    const long long MAX_ATTEMPTS = 100000000; 

    std::cout << "开始猴子排序... (这可能需要很长时间，取决于运气)\n";
    
    while (!isSorted(arr)) {
        // 随机打乱数组
        std::shuffle(arr.begin(), arr.end(), gen);
        attempts++;

        // 每 100 万次打印一次进度，避免刷屏
        if (attempts % 1000000 == 0) {
            std::cout << "已尝试 " << attempts / 1000000 << " 百万次...\n";
        }

        // 安全检查：如果尝试次数过多，强制退出
        if (attempts >= MAX_ATTEMPTS) {
            std::cerr << "\n错误：达到最大尝试次数 (" << MAX_ATTEMPTS << ")，排序失败。\n";
            std::cerr << "建议：猴子排序仅适用于极小规模数据（如 n <= 10）。\n";
            return false;
        }
    }

    std::cout << "\n排序成功！总共打乱了 " << attempts << " 次。\n";
    return true;
}

int main() {
    int n;
    
    // 1. 获取用户输入
    std::cout << "=== 猴子排序 (Bogo Sort) 演示 ===\n";
    std::cout << "请输入要排序的元素个数 (建议 <= 10，否则可能永远跑不完): ";
    if (!(std::cin >> n) || n <= 0) {
        std::cerr << "输入无效，请输入一个正整数。\n";
        return 1;
    }

    // 强烈建议限制输入大小，因为阶乘增长极快
    if (n > 12) {
        std::cout << "警告：元素个数过多，猴子排序效率极低，程序可能会运行非常久。\n";
        char confirm;
        std::cout << "确定要继续吗？(y/n): ";
        std::cin >> confirm;
        if (confirm != 'y' && confirm != 'Y') {
            return 0;
        }
    }

    std::vector<int> arr(n);
    std::cout << "请依次输入 " << n << " 个整数:\n";
    for (int i = 0; i < n; ++i) {
        std::cout << "元素 [" << i + 1 << "]: ";
        std::cin >> arr[i];
    }

    // 显示原始数组
    std::cout << "\n原始数组: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n--------------------------------\n";

    // 执行排序
    auto start = std::chrono::high_resolution_clock::now();
    bool success = bogoSort(arr);
    auto end = std::chrono::high_resolution_clock::now();
    
    // 计算耗时
    std::chrono::duration<double> duration = end - start;

    if (success) {
        std::cout << "排序结果: ";
        for (int num : arr) {
            std::cout << num << " ";
        }
        std::cout << "\n耗时: " << duration.count() << " 秒\n";
    }

    return 0;
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
