时间复杂度:你要排序的数字中的最大值!!!

时间复杂度:$O(N~max~)$

创建和启动线程：

为每个数组元素创建一个线程，并在线程中执行排序操作。

在启动线程时，使用一个条件变量和互斥锁来同步所有线程的开始时间，确保所有线程在同一时刻开始运行。

线程暂停：

在每个线程中，让线程暂停一段时间，具体的暂停时间与对应的数字成比例。比如，数字越大，暂停时间越长。

将数字插入结果数组：

在暂停结束后，使用互斥锁保护共享的结果数组，将数字插入结果数组。

这样可以确保多个线程不会同时访问和修改结果数组，避免数据竞争。

等待所有线程完成：

使用 join 方法确保主线程等待所有子线程执行完毕。

输出排序后的数组：

最后，输出结果数组，它应该是按从小到大排序好的数组。

#include <iostream>
#include <thread>
#include <vector>
#include <mutex>
#include <chrono>
#include <condition_variable>
#include <cstdlib> 
#include <ctime> 
#include <algorithm>
using namespace std;

// 共享的结果数组
vector<int> sortedArray;
mutex mtx; // 互斥锁保护数组
condition_variable cv;
bool start = false; // 开始信号

void sortElement(int value) {
    {
        unique_lock<mutex> lock(mtx);
        cv.wait(lock, [] { return start; });
    }
    // 让线程暂停value毫秒（乘以20扩大时间差异）
    this_thread::sleep_for(chrono::milliseconds(value * 20));
    // 加锁以
    lock_guard<mutex> lock(mtx);
    sortedArray.push_back(value);
}

int main() {
    srand(time(0));
    vector<int> arr(100);//100个
    cout << "Random elements: ";
    for (int i = 0; i < 100; ++i) {
        arr[i] = rand() % 100 + 1; // 生成 1 到 100 的随机数
        cout << arr[i] << " ";
    }
    cout << endl;
    vector<thread> threads;
    for (int value : arr) {
        threads.push_back(thread(sortElement, value));
    }

    {//大括号限制作用域
        lock_guard<mutex> lock(mtx);
        start = true;
    }
    cv.notify_all(); // 通知所有线程开始运行

    for (auto& th : threads) {
        th.join();
    }
    cout << "Sorted array: ";
    for (int value : sortedArray) {
        cout << value << " ";
    }
    cout << endl;
    cout << "Is Sorted? : ";
    if (is_sorted(sortedArray.begin(), sortedArray.end())) cout << "Yes";
    else cout << "No";
    return 0;
}

最后一个用来检测数组是否排序，此方法有的时候会抽风，但概率不大。