c++ 20 快速排序模板实现

首先为了避免大家对快速排序不熟悉所以先简单说一下快速排序的原理：

假定有一个数组定义如下：

要完成快速排序，第一步需要选择一个元素然后进行 partition 过程，这个过程的本质就是分区，把比自己小的都扔到左边，把比自己大的都扔到右边，比如我们选择 4 ，然后 partition 完成后的结果就是：

接着我们只需要递归的对 4 左右的两个区间调用快速排序就好了：

了解了基本的原理以后，这里我们使用模板实现来使得算法更加通用，顺便也是对一部分 c++20 特性的运用和总结。

首先我们的快速排序算法应该支持用户直接传入任何类型的容器：

这里对 Range 有一个约束 element_comparable：

也就是说

1) 这个容器要符合一个 range （也就是包含 begin 和 end）

2）容器内包含的元素必须是可比较的 （three_way 指的是 <=> 运算符）

default_less_compare 是默认的比较函数，定义如下：

接着进入 _quick_sort 的实现，参数用 begin 和 end 传入 range 的范围：

可以看到我们接收三个参数，两个迭代器表示 range 的范围， comp 则是用于比较的谓词对象，同样有一个约束 predicate，定义如下：

这里的两个条件一个是可调用，第二个则是返回类型（可转换）为 bool，注意这里定义的实际是变长参数，而我们在 _quick_sort 规定了参数的个数为两个。

_quick_sort 中做的事情就是刚刚说过的 partition 和递归的做 _quick_sort，看一下 partition 的实现：

这里用的也是比较容易理解的填坑法，对于一个序列 {3, 1, 4, 2} 进行 partition 过程如下：

partition 结束后的序列为 {1, 2, 3, 4}，返回的下标为 2

返回到 _quick_sort 后只需要递归的对左右分区即 [0, 2) 和 [3, 4) 递归做快排即可。

另外我们还希望支持自定义 Compare 函数，重载一个 quick_sort 版本如下：

接收用户传入的比较函数并传入即可，因为我们在 _quick_sort 处对 comp 函数做了约束因此不用担心什么。