接下來，我們會討論快速排序的更多細節(jié)

標志位的選取

在上篇博文中，我們講到了標志位的選取一般是取數(shù)組第一個元素，但是由于快排的本質是通過O(n)的時間排序好一個數(shù)（標志位）以及劃分兩個相對大小的數(shù)組（小于標志位的數(shù)組和大于標志位的數(shù)組），如果標志位是整個數(shù)組的最大值或者最小值，會導致本輪排序在劃分數(shù)組時不能獲得優(yōu)質的結果

什么樣的標志位才是效率最高的呢？

1. 最好的標志位是數(shù)組的中位數(shù)，本輪排序會將數(shù)組劃分為相同大小的兩個子數(shù)組，由此每輪劃分的元素最多，排序效果最好
2. 中位數(shù)的選取最快也需要 O(n) 的時間，每輪排序取額外選取中位數(shù)得不償失，學過統(tǒng)計學，我們知道，可以用樣本的中位數(shù)去估計真實的中位數(shù)

基于以上兩點，我們可以試試三分取中法

三分取中法

三分取中法的大致思路如下：

首先，我們找出數(shù)組中位置在第一個的值，最后一個的值和最中間的值

然后，我們選取上述三個數(shù)中的中位數(shù)作為我們本輪排序的標志位

這樣選擇的標志位雖然不一定是整個數(shù)組的中位數(shù)，但是比起選擇第一個元素，要科學不少，而且在數(shù)組基本有序時，也能有效的避免最差的時間復雜度。

如果對于標志位的選取更加嚴格，我們可以從 2*(n-1)位中選取中位數(shù)，n的數(shù)值越大，中位數(shù)越有效，但是選取中位數(shù)所消耗的時間也越多

重復鍵值

我們在使用快速排序時，有時候會遇到許多元素相等的項，譬如

1. 按照年齡排序
2. 郵件列表中的重復郵件
3. 根據(jù)地名排序

而這類情況往往有幾個特征

1. 數(shù)組元素很多
2. 相對于數(shù)組元素的個數(shù)，元素的種類很少（很大一部分元素相等）

特別，當數(shù)組中的元素全相同時，如果我們在元素項與標志位相等時繼續(xù)排序，時間復雜度會驟升至 O(n^2)，如果我們在元素項與標志位相等時停止，也會產(chǎn)生 O(nlgn) 的時間復雜度。

接下來我們介紹快排的一種優(yōu)化，在數(shù)組元素基本相同時，可以取得近似 O(n)的排序效果

三路快排

在快速排序中，我們會找到標志位，然后將其排序到對應位置，保證標志位前面的數(shù)小于標志位，標志位后面的數(shù)大于標志位。如果我們將標志位擴展為數(shù)組的幾個相等元素，就像這樣

數(shù)組被分為三部分

1. lt 和 gt 之間的數(shù)都等于 v
2. lt 左邊的數(shù)都小于 v
3. gt 右邊的數(shù)都大于 v

對比普通快排算法，我們新增了 lt與 gt兩個標志用來存儲數(shù)值等于 v的起始與結束位置。

算法代碼如下

func sort3way(arr []int, low int, high int) {
    if high <= low {
        return
    }
    lt, gt, v := low, high, arr[low]
    i := low
    for i <= gt {
        cmp := arr[i] - v
        if cmp < 0 {
            exch(arr, lt, i)
            lt++
            i++
        } else if cmp > 0 {
            exch(arr, i, gt)
            gt--
        } else {
            i++
        }
    }
    sort3way(arr, low, lt-1)
    sort3way(arr, gt+1, high)
}

在數(shù)組中大部分元素相等時，我們的三路快排算法會演化成數(shù)組的遍歷，從而時間復雜度接近 O(n)

參考文獻：
Dynamic Connectivity - 普林斯頓大學 | Coursera