本文介绍了快速排序的并行版实现，通过C++标准库中的std::partition和并行执行策略std::execution::par，实现了高效的并行排序。代码展示了如何随机选择枢轴元素，并通过分区操作将数组分为小于和大于枢轴的两部分，然后递归地对子数组进行排序。文章还强调了实现快速排序的两个关键要求：必须使用前进迭代器，且元素必须支持比较操作或重载operator<。本文为C++开发者提供了并行排序的实用技巧，帮助提升排序算法的性能。
快速排序
快速排序并行版实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| template<typename ForwardIt>
inline void quick_sort(ForwardIt first, ForwardIt last) {
if(first == last) return;
decltype(std::distance(first, last)) temp = rand() % std::distance(first, last);
auto pivot = *std::next(first, temp);
auto middle1 = std::partition(std::execution::par, first, last, [pivot](const auto& em){
return em < pivot;
});
auto middle2 = std::partition(std::execution::par, middle1, last, [pivot](const auto& em){
return !(pivot < em);
});
quick_sort(first, middle1);
quick_sort(middle2, last);
}
|
使用要求：
- 必须是前进迭代器
- 元素必须是可比较的，或有
operator<运算符重载