用C++实现多线程快速排序中的并行排序

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

// 快速排序函数
void quickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int pivot = arr[left]; // 选择第一个元素作为基准值
    int i = left, j = right;
    
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    
    arr[i] = pivot;
    
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

// 并行排序函数
void parallelSort(std::vector<int>& arr, int numThreads) {
    int size = arr.size();
    int chunkSize = size / numThreads;
    
    std::vector<std::thread> threads;
    
    // 创建多个线程进行排序
    for (int i = 0; i < numThreads; i++) {
        int left = i * chunkSize;
        int right = (i == numThreads - 1) ? size - 1 : (left + chunkSize - 1);
        
        threads.emplace_back(quickSort, std::ref(arr), left, right);
    }
    
    // 等待所有线程排序完成
    for (auto& thread : threads) {
        thread.join();
    }
    
    // 合并排序好的子数组
    for (int i = 1; i < numThreads; i++) {
        int left = i * chunkSize;
        int right = (i == numThreads - 1) ? size - 1 : (left + chunkSize - 1);
        
        int j = left;
        while (j <= right) {
            int temp = arr[j];
            int k = j - 1;
            while (k >= 0 && arr[k] > temp) {
                arr[k + 1] = arr[k];
                k--;
            }
            arr[k + 1] = temp;
            j++;
        }
    }
}

int main() {
    std::vector<int> arr = {9, 3, 2, 8, 5, 1, 7, 6, 4};
    int numThreads = 4; // 设置线程数量
    
    parallelSort(arr, numThreads);
    
    // 输出排序结果
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}