面试题：C++ 多线程快速排序实现

Question

利用C++ 的多线程库（如C++11的<thread>）实现多线程版本的快速排序。要求合理划分任务，充分利用多核处理器的性能优势，提高大规模数据的排序效率。请描述设计思路并给出关键代码实现，同时分析可能存在的性能瓶颈及解决方案。

Answer 1

设计思路

1. 任务划分：将待排序数组递归地划分为较小的子数组，每个子数组作为一个独立的任务。
2. 多线程处理：为每个子数组的排序任务创建一个线程，利用多核处理器并行处理这些任务。
3. 合并结果：当所有子数组排序完成后，将这些有序的子数组合并为一个完整的有序数组。

关键代码实现

#include <iostream>
#include <thread>
#include <vector>
#include <algorithm>
#include <functional>
#include <future>

// 划分函数
int partition(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;
}

// 多线程快速排序
void parallelQuickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        // 创建两个线程来分别处理左右子数组
        std::future<void> leftFuture, rightFuture;
        if (pi - low > 1) {
            leftFuture = std::async(std::launch::async, parallelQuickSort, std::ref(arr), low, pi - 1);
        } else {
            parallelQuickSort(arr, low, pi - 1);
        }

        if (high - pi > 1) {
            rightFuture = std::async(std::launch::async, parallelQuickSort, std::ref(arr), pi + 1, high);
        } else {
            parallelQuickSort(arr, pi + 1, high);
        }

        // 等待线程完成
        if (pi - low > 1) {
            leftFuture.get();
        }
        if (high - pi > 1) {
            rightFuture.get();
        }
    }
}

性能瓶颈及解决方案

1. 线程创建和销毁开销：频繁创建和销毁线程会带来额外的开销。
   • 解决方案：使用线程池，预先创建一定数量的线程，任务到来时直接分配给线程池中的线程，避免频繁创建和销毁线程。
2. 负载均衡：如果子数组划分不均匀，可能导致某些线程处理的任务过重，而其他线程闲置。
   • 解决方案：采用更智能的划分策略，例如根据数据的分布来划分，或者在运行时动态调整任务分配，确保每个线程的工作量大致相同。
3. 锁竞争：如果在多线程环境下共享资源（如全局变量），可能会出现锁竞争，降低并行效率。
   • 解决方案：尽量避免共享资源，将数据按线程进行隔离。如果必须共享资源，可以使用无锁数据结构或更细粒度的锁机制来减少竞争。