#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <cmath> // 用于计算阶乘
 
using namespace std;
 
// 计算阶乘（用于时间复杂度估计）
long long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}
 
// 检查数组是否已排序
bool isSorted(const vector<int>& arr) {
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}
 
// 猴子排序（带时间复杂度输出）
void bogoSort(vector<int>& arr) {
    auto startTime = chrono::high_resolution_clock::now(); // 记录开始时间
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine engine(seed);
 
    int attempts = 0;
    const int n = arr.size();
    const long long worstCaseComplexity = factorial(n); // 最坏情况 O(n!)
 
    cout << "猴子排序（Bogo Sort）时间复杂度分析：" << endl;
    cout << "数组大小 n = " << n << endl;
    cout << "最坏情况时间复杂度: O(n!) = " << worstCaseComplexity << " 次尝试" << endl;
    cout << "平均情况时间复杂度: O(n * n!)" << endl;
    cout << "----------------------------------" << endl;
 
    while (!isSorted(arr)) {
        shuffle(arr.begin(), arr.end(), engine);
        attempts++;
 
        // 每10000次尝试输出一次当前状态
        if (attempts % 10000 == 0) {
            auto currentTime = chrono::high_resolution_clock::now();
            auto elapsedTime = chrono::duration_cast<chrono::milliseconds>(currentTime - startTime).count();
 
            cout << "已尝试 " << attempts << " 次 | ";
            cout << "当前时间复杂度: O(" << attempts << ") | ";
            cout << "已运行时间: " << elapsedTime << " ms" << endl;
        }
    }
 
    auto endTime = chrono::high_resolution_clock::now();
    auto totalTime = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
 
    cout << "----------------------------------" << endl;
    cout << "排序完成！" << endl;
    cout << "实际尝试次数: " << attempts << endl;
    cout << "理论最坏情况尝试次数: O(n!) = " << worstCaseComplexity << endl;
    cout << "总运行时间: " << totalTime << " ms" << endl;
}
 
int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9,4,76,346}; // 测试数组（建议n≤6，否则可能极慢）
 
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
    cout << endl;
 
    bogoSort(arr);
 
    cout << "排序后: ";
    for (int num : arr) cout << num << " ";
    cout << endl;
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8Y21hdGg+IC8vIOeUqOS6juiuoeeul+mYtuS5mAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIOiuoeeul+mYtuS5mO+8iOeUqOS6juaXtumXtOWkjeadguW6puS8sOiuoe+8iQpsb25nIGxvbmcgZmFjdG9yaWFsKGludCBuKSB7CiAgICBpZiAobiA8PSAxKSByZXR1cm4gMTsKICAgIHJldHVybiBuICogZmFjdG9yaWFsKG4gLSAxKTsKfQoKLy8g5qOA5p+l5pWw57uE5piv5ZCm5bey5o6S5bqPCmJvb2wgaXNTb3J0ZWQoY29uc3QgdmVjdG9yPGludD4mIGFycikgewogICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCBhcnIuc2l6ZSgpIC0gMTsgKytpKSB7CiAgICAgICAgaWYgKGFycltpXSA+IGFycltpICsgMV0pIHsKICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiB0cnVlOwp9CgovLyDnjLTlrZDmjpLluo/vvIjluKbml7bpl7TlpI3mnYLluqbovpPlh7rvvIkKdm9pZCBib2dvU29ydCh2ZWN0b3I8aW50PiYgYXJyKSB7CiAgICBhdXRvIHN0YXJ0VGltZSA9IGNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOjpub3coKTsgLy8g6K6w5b2V5byA5aeL5pe26Ze0CiAgICB1bnNpZ25lZCBzZWVkID0gY2hyb25vOjpzeXN0ZW1fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpOwogICAgZGVmYXVsdF9yYW5kb21fZW5naW5lIGVuZ2luZShzZWVkKTsKICAgIAogICAgaW50IGF0dGVtcHRzID0gMDsKICAgIGNvbnN0IGludCBuID0gYXJyLnNpemUoKTsKICAgIGNvbnN0IGxvbmcgbG9uZyB3b3JzdENhc2VDb21wbGV4aXR5ID0gZmFjdG9yaWFsKG4pOyAvLyDmnIDlnY/mg4XlhrUgTyhuISkKCiAgICBjb3V0IDw8ICLnjLTlrZDmjpLluo/vvIhCb2dvIFNvcnTvvInml7bpl7TlpI3mnYLluqbliIbmnpDvvJoiIDw8IGVuZGw7CiAgICBjb3V0IDw8ICLmlbDnu4TlpKflsI8gbiA9ICIgPDwgbiA8PCBlbmRsOwogICAgY291dCA8PCAi5pyA5Z2P5oOF5Ya15pe26Ze05aSN5p2C5bqmOiBPKG4hKSA9ICIgPDwgd29yc3RDYXNlQ29tcGxleGl0eSA8PCAiIOasoeWwneivlSIgPDwgZW5kbDsKICAgIGNvdXQgPDwgIuW5s+Wdh+aDheWGteaXtumXtOWkjeadguW6pjogTyhuICogbiEpIiA8PCBlbmRsOwogICAgY291dCA8PCAiLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSIgPDwgZW5kbDsKCiAgICB3aGlsZSAoIWlzU29ydGVkKGFycikpIHsKICAgICAgICBzaHVmZmxlKGFyci5iZWdpbigpLCBhcnIuZW5kKCksIGVuZ2luZSk7CiAgICAgICAgYXR0ZW1wdHMrKzsKCiAgICAgICAgLy8g5q+PMTAwMDDmrKHlsJ3or5XovpPlh7rkuIDmrKHlvZPliY3nirbmgIEKICAgICAgICBpZiAoYXR0ZW1wdHMgJSAxMDAwMCA9PSAwKSB7CiAgICAgICAgICAgIGF1dG8gY3VycmVudFRpbWUgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CiAgICAgICAgICAgIGF1dG8gZWxhcHNlZFRpbWUgPSBjaHJvbm86OmR1cmF0aW9uX2Nhc3Q8Y2hyb25vOjptaWxsaXNlY29uZHM+KGN1cnJlbnRUaW1lIC0gc3RhcnRUaW1lKS5jb3VudCgpOwogICAgICAgICAgICAKICAgICAgICAgICAgY291dCA8PCAi5bey5bCd6K+VICIgPDwgYXR0ZW1wdHMgPDwgIiDmrKEgfCAiOwogICAgICAgICAgICBjb3V0IDw8ICLlvZPliY3ml7bpl7TlpI3mnYLluqY6IE8oIiA8PCBhdHRlbXB0cyA8PCAiKSB8ICI7CiAgICAgICAgICAgIGNvdXQgPDwgIuW3sui/kOihjOaXtumXtDogIiA8PCBlbGFwc2VkVGltZSA8PCAiIG1zIiA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KCiAgICBhdXRvIGVuZFRpbWUgPSBjaHJvbm86OmhpZ2hfcmVzb2x1dGlvbl9jbG9jazo6bm93KCk7CiAgICBhdXRvIHRvdGFsVGltZSA9IGNocm9ubzo6ZHVyYXRpb25fY2FzdDxjaHJvbm86Om1pbGxpc2Vjb25kcz4oZW5kVGltZSAtIHN0YXJ0VGltZSkuY291bnQoKTsKCiAgICBjb3V0IDw8ICItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIiA8PCBlbmRsOwogICAgY291dCA8PCAi5o6S5bqP5a6M5oiQ77yBIiA8PCBlbmRsOwogICAgY291dCA8PCAi5a6e6ZmF5bCd6K+V5qyh5pWwOiAiIDw8IGF0dGVtcHRzIDw8IGVuZGw7CiAgICBjb3V0IDw8ICLnkIborrrmnIDlnY/mg4XlhrXlsJ3or5XmrKHmlbA6IE8obiEpID0gIiA8PCB3b3JzdENhc2VDb21wbGV4aXR5IDw8IGVuZGw7CiAgICBjb3V0IDw8ICLmgLvov5DooYzml7bpl7Q6ICIgPDwgdG90YWxUaW1lIDw8ICIgbXMiIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewogICAgdmVjdG9yPGludD4gYXJyID0gezMsIDEsIDQsIDEsIDUsIDksNCw3NiwzNDZ9OyAvLyDmtYvor5XmlbDnu4TvvIjlu7rorq5u4omkNu+8jOWQpuWImeWPr+iDveaegeaFou+8iQoKICAgIGNvdXQgPDwgIuaOkuW6j+WJjTogIjsKICAgIGZvciAoaW50IG51bSA6IGFycikgY291dCA8PCBudW0gPDwgIiAiOwogICAgY291dCA8PCBlbmRsOwoKICAgIGJvZ29Tb3J0KGFycik7CgogICAgY291dCA8PCAi5o6S5bqP5ZCOOiAiOwogICAgZm9yIChpbnQgbnVtIDogYXJyKSBjb3V0IDw8IG51bSA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0=