首先為了避免大家對(duì)快速排序不熟悉所以先簡(jiǎn)單說(shuō)一下快速排序的原理：

假定有一個(gè)數(shù)組定義如下：

要完成快速排序，第一步需要選擇一個(gè)元素然后進(jìn)行 partition 過(guò)程，這個(gè)過(guò)程的本質(zhì)就是分區(qū)，把比自己小的都扔到左邊，把比自己大的都扔到右邊，比如我們選擇 4?，然后 partition 完成后的結(jié)果就是：

接著我們只需要遞歸的對(duì)?4 左右的兩個(gè)區(qū)間調(diào)用快速排序就好了：

了解了基本的原理以后，這里我們使用模板實(shí)現(xiàn)來(lái)使得算法更加通用，順便也是對(duì)一部分 c++20 特性的運(yùn)用和總結(jié)。

首先我們的快速排序算法應(yīng)該支持用戶直接傳入任何類型的容器：

這里對(duì) Range 有一個(gè)約束 element_comparable：

也就是說(shuō)

1) 這個(gè)容器要符合一個(gè) range （也就是包含 begin 和 end）

2）容器內(nèi)包含的元素必須是可比較的 （three_way 指的是 <=> 運(yùn)算符）

default_less_compare 是默認(rèn)的比較函數(shù)，定義如下：

接著進(jìn)入 _quick_sort 的實(shí)現(xiàn)，參數(shù)用 begin 和 end 傳入 range 的范圍：

可以看到我們接收三個(gè)參數(shù)，兩個(gè)迭代器表示 range 的范圍， comp 則是用于比較的謂詞對(duì)象，同樣有一個(gè)約束 predicate，定義如下：

這里的兩個(gè)條件一個(gè)是可調(diào)用，第二個(gè)則是返回類型（可轉(zhuǎn)換）為?bool，注意這里定義的實(shí)際是變長(zhǎng)參數(shù)，而我們?cè)?_quick_sort 規(guī)定了參數(shù)的個(gè)數(shù)為兩個(gè)。

_quick_sort 中做的事情就是剛剛說(shuō)過(guò)的 partition 和遞歸的做 _quick_sort，看一下 partition 的實(shí)現(xiàn)：

這里用的也是比較容易理解的填坑法，對(duì)于一個(gè)序列 {3, 1, 4, 2} 進(jìn)行 partition 過(guò)程如下：

partition 結(jié)束后的序列為 {1, 2, 3, 4}，返回的下標(biāo)為 2

返回到 _quick_sort 后只需要遞歸的對(duì)左右分區(qū)即 [0, 2) 和 [3, 4) 遞歸做快排即可。

另外我們還希望支持自定義 Compare 函數(shù)，重載一個(gè) quick_sort 版本如下：

接收用戶傳入的比較函數(shù)并傳入即可，因?yàn)槲覀冊(cè)?_quick_sort 處對(duì) comp 函數(shù)做了約束因此不用擔(dān)心什么。