如何在递归快速排序算法中使用每个线程一次？

嘿，我懂你想让系统里的每一个可用线程都参与到快速排序里，又不想因为无限制创建线程导致系统过载对吧？这确实是递归并行化里的常见问题，直接给每个递归调用开线程绝对会炸——毕竟快排的递归深度可不浅，线程数会指数级增长。咱们来一步步实现只用到系统全部线程一次的并行快排。

首先得明确核心思路：只在还有剩余可用线程的时候，才为递归分支创建新线程；一旦线程数达到系统上限，就回到串行递归。这样既能把所有线程都利用起来，又不会出现线程泛滥的问题。

先给你补全带并行控制的完整代码，里面我加了详细的注释：

#include <iostream>
#include <vector>
#include <thread>
#include <atomic>

// 用原子变量跟踪活跃线程数，保证多线程下的安全访问
std::atomic<int> active_threads(1); // 初始值设为1，因为主线程已经在运行了

// 快排的分区函数，这部分是基础逻辑，之前你省略了我补上
int partition(std::vector<double>& v, int begin, int end) {
    double pivot = v[end];
    int i = begin - 1;
    for (int j = begin; j < end; ++j) {
        if (v[j] <= pivot) {
            ++i;
            std::swap(v[i], v[j]);
        }
    }
    std::swap(v[i+1], v[end]);
    return i + 1;
}

void quicksort(std::vector<double>& v, int const begin, int const end) {
    // 递归终止条件：子数组长度小于等于1
    if (begin >= end) return;

    // 先完成分区，拿到基准元素的位置
    int pivot_idx = partition(v, begin, end);

    // 获取系统支持的最大并发线程数，一般等于CPU核心数
    int const max_threads = std::thread::hardware_concurrency();
    // 万一系统不支持这个函数（返回0），咱们给个默认值兜底
    int const actual_max = max_threads == 0 ? 4 : max_threads;

    // 检查是否还有剩余线程名额
    if (active_threads < actual_max) {
        // 先增加活跃线程计数
        active_threads++;
        // 创建新线程处理左半部分的递归
        std::thread sort_left([&v, begin, pivot_idx]() {
            quicksort(v, begin, pivot_idx - 1);
            // 线程完成后，把活跃线程数减回去
            active_threads--;
        });
        // 分离线程，让它独立运行，不用当前线程等待
        sort_left.detach();
        // 当前线程（主线程或者其他已有的线程）处理右半部分
        quicksort(v, pivot_idx + 1, end);
    } else {
        // 没有剩余线程了，串行处理两个分支
        quicksort(v, begin, pivot_idx - 1);
        quicksort(v, pivot_idx + 1, end);
    }
}

int main() {
    std::vector<double> test_nums = {3.1, 1.4, 2.7, 5.5, 4.2, 0.9, 6.3, 7.8, 0.2};
    quicksort(test_nums, 0, test_nums.size() - 1);

    // 等待所有子线程完成，因为用了detach，所以这里用循环等待活跃线程数回到1（只剩主线程）
    while (active_threads > 1) {
        std::this_thread::yield(); // 让出CPU，避免空转浪费资源
    }

    // 输出排序后的结果
    for (double num : test_nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

再给你拆解几个关键要点：

• 原子计数器：用std::atomic<int>而不是普通int，是因为多个线程会同时修改这个计数，原子操作能避免竞态条件，保证计数准确。
• 线程创建控制：每次创建新线程前都检查当前活跃线程数是否小于系统上限，这样最多只会创建max_threads - 1个子线程，加上主线程刚好把所有可用线程用满。
• 线程分离与等待：用detach()让子线程独立运行，不用父线程一直等着；主函数里的循环是为了确保所有子线程都完成排序后再输出结果，避免数据还没排好就打印。
• 兜底处理：如果std::thread::hardware_concurrency()返回0（有些老旧系统可能这样），咱们默认用4个线程，保证代码能正常运行。

另外还有个小建议：如果想更严谨地等待线程完成，可以用std::condition_variable代替主函数里的循环，不过对于这个场景来说，简单的循环已经足够用了。

备注：内容来源于stack exchange，提问作者tiredUser