🐒 猴子排序 (Bogosort) - 最"搞笑"的排序算法

猴子排序（Bogosort），也被称为随机排序、愚蠢排序或猴子无限排序，是一种极其低效但概念上非常有趣的排序算法。

🤔 什么是猴子排序？

猴子排序的核心思想来源于"无限猴子定理"：

"让一只猴子随机敲击键盘，经过无限时间后，它几乎必然能打出莎士比亚的全集。"

猴子排序就是这个思想在排序中的体现：

🔁 算法原理

// 猴子排序的伪代码
while (数组不是有序的) {
    随机打乱数组的所有元素
}

💻 C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

class BogoSort {
private:
    std::random_device rd;
    std::mt19937 gen;
    
public:
    BogoSort() : gen(rd()) {}
    
    // 检查数组是否已排序
    bool isSorted(const std::vector<int>& arr) {
        for (size_t i = 1; i < arr.size(); i++) {
            if (arr[i] < arr[i-1]) {
                return false;
            }
        }
        return true;
    }
    
    // 随机打乱数组
    void shuffle(std::vector<int>& arr) {
        std::shuffle(arr.begin(), arr.end(), gen);
    }
    
    // 猴子排序主函数
    void sort(std::vector<int>& arr) {
        int attempts = 0;
        while (!isSorted(arr)) {
            shuffle(arr);
            attempts++;
            
            // 可选：显示进度（小数组）
            if (arr.size() <= 10 && attempts % 100000 == 0) {
                std::cout << "尝试次数: " << attempts << std::endl;
            }
        }
        std::cout << "总共尝试了 " << attempts << " 次!" << std::endl;
    }
};

// 使用示例
int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5};
    
    std::cout << "原始数组: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << std::endl;
    
    BogoSort bogo;
    bogo.sort(arr);
    
    std::cout << "排序后: ";
    for (int x : arr) std::cout << x << " ";
    std::cout << std::endl;
    
    return 0;
}

📊 时间复杂度分析

理论复杂度：

• 最好情况: O(n) - 第一次就随机排好了
• 平均情况: O((n+1)!) - 超级恐怖！
• 最坏情况: O(∞) - 永远排不好

具体数字：

数组大小 | 可能排列数 | 平均尝试次数
--------|-----------|-------------
1       | 1         | 1
2       | 2         | 2
3       | 6         | 6
4       | 24        | 24
5       | 120       | 120
6       | 720       | 720
10      | 3,628,800 | 3,628,800

🤡 更多"搞笑"排序算法

1. 🐢 睡眠排序 (Sleep Sort)

#include <iostream>
#include <vector>
#include <thread>
#include <chrono>

void sleepSort(const std::vector<int>& arr) {
    std::vector<std::thread> threads;
    
    for (int x : arr) {
        threads.emplace_back([x]() {
            std::this_thread::sleep_for(std::chrono::milliseconds(x));
            std::cout << x << " ";
        });
    }
    
    for (auto& t : threads) {
        t.join();
    }
    std::cout << std::endl;
}

2. 🎨 随机选择排序 (Bozo Sort)

class BozoSort {
private:
    std::random_device rd;
    std::mt19937 gen;
    std::uniform_int_distribution<> dis;
    
public:
    BozoSort(int size) : gen(rd()), dis(0, size-1) {}
    
    bool isSorted(const std::vector<int>& arr) {
        for (size_t i = 1; i < arr.size(); i++) {
            if (arr[i] < arr[i-1]) return false;
        }
        return true;
    }
    
    void sort(std::vector<int>& arr) {
        int attempts = 0;
        while (!isSorted(arr)) {
            // 随机选择两个不同位置
            int i = dis(gen);
            int j = dis(gen);
            if (i != j) {
                std::swap(arr[i], arr[j]);
            }
            attempts++;
        }
        std::cout << "Bozo排序尝试了 " << attempts << " 次" << std::endl;
    }
};

3. 🐢 慢排序 (Slow Sort)

void slowSort(std::vector<int>& arr, int i, int j) {
    if (i >= j) return;
    
    int m = (i + j) / 2;
    
    // 递归排序前半部分
    slowSort(arr, i, m);
    // 递归排序后半部分
    slowSort(arr, m + 1, j);
    
    // 将最大值移到最后
    if (arr[m] > arr[j]) {
        std::swap(arr[m], arr[j]);
    }
    
    // 递归排序前半部分（包括新移动的最大值）
    slowSort(arr, i, j - 1);
}

4. 🎯 随机快速排序 (恶意版本)

class WorstQuickSort {
public:
    static void worstPivotQuickSort(std::vector<int>& arr, int low, int high) {
        if (low < high) {
            // 总是选择最大值作为枢轴（最坏情况）
            int pivot = partitionWorst(arr, low, high);
            worstPivotQuickSort(arr, low, pivot - 1);
            worstPivotQuickSort(arr, pivot + 1, high);
        }
    }
    
private:
    static int partitionWorst(std::vector<int>& arr, int low, int high) {
        // 总是选择最后一个元素作为枢轴
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        return i + 1;
    }
};

5. 🎭 表演排序 (Drama Sort)

class DramaSort {
public:
    void dramaSort(std::vector<int>& arr) {
        std::cout << "🎭 欢迎观看戏剧排序表演！" << std::endl;
        
        int round = 1;
        while (!isSorted(arr)) {
            std::cout << "第 " << round << " 幕表演开始..." << std::endl;
            
            // 每个元素"表演"
            for (size_t i = 0; i < arr.size(); i++) {
                std::cout << "演员 " << arr[i] << " 正在表演..." << std::endl;
                std::this_thread::sleep_for(std::chrono::milliseconds(100));
            }
            
            // 表演结束后随机交换
            std::shuffle(arr.begin(), arr.end(), gen);
            std::cout << "幕间休息，重新安排演员位置..." << std::endl;
            std::this_thread::sleep_for(std::chrono::milliseconds(500));
            
            round++;
            if (round > 10) {
                std::cout << "观众不耐烦了，强制结束表演！" << std::endl;
                break;
            }
        }
    }
};

📊 搞笑排序算法性能对比

⚠️ 为什么这些算法如此低效？

1. 概率极低：n个元素有n!种排列，只有一种是有序的
2. 无记忆性：每次操作都完全独立
3. 无优化：不会从错误中学习
4. 违反排序原则：没有利用比较和交换的数学性质

📝 什么时候用这些搞笑排序？

答案：永远不要用！ 😄

这些搞笑排序的主要用途：

• 教学示例（展示什么是"坏"算法）
• 测试随机数生成器
• 编程笑话和娱乐
• 面试中的"陷阱"问题
• 证明某些问题需要更好的算法

🔚 总结

猴子排序虽然在理论上可以工作，但在实践中完全不可用。通过对比这些搞笑算法，我们更能体会到高效算法的价值：

记住：猴子排序告诉我们，正确的算法比蛮力更重要！ 🐒

就像我们之前讨论的sqrt函数优化一样，选择正确的工具和方法才是提升性能的关键。无论是数学计算还是排序算法，都有其最优解。