C++ 快速排序的实现

快速排序

快速排序并行版实现

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);
}

使用要求：

1. 必须是前进迭代器
2. 元素必须是可比较的，或有operator<运算符重载