再探快速排序 → 遞進式演進，是否更容易理解？
開心一刻
爺爺有退休金，奶奶沒有
可奶奶很要強
為了不讓爺爺看不起，她找了份環衛的工作
結果要早起，她起不來
現在爺爺每天要早起掃大街
前情回顧
關於快排，樓主之前寫過兩篇關於它的文章
排序之快速排序 → 基本版實現，排序之快速排序 → 基本版優化
感覺講的有點突兀，看過之後你們的表情是這樣的
貼心的我實在是難以忍受你們那無辜的小眼神，決定讓你們的表情變成這樣
兩區域劃分
問題描述：給定一個整型數組 arr 和一個整數 target ，請把小於等於 target 的數放在數組的左邊，大於 target 的數放在數組的右邊
常規實現
如果不做任何限制，我相信大家很容易想到如下方法
準備一個新數組，然後遍歷 arr ， arr 素逐個與 target 進行比較
小於等於 target 的元素從左往右放入到新數組中，大於 target 的元素從右往左放入到新數組中
當 arr 遍歷完，新數組中的元素順序即是：小於等於 target 的數在左邊，大於 target 的數在右邊
我們來看程式碼實現
假設 arr 是 [9,8,3,2,6,4,5,0,1,1,1] ， target 是 7，那麼得到的結果是 [3,2,6,4,5,0,1,1,1,8,9]
細心的小夥伴會大聲道：你這不對，3 怎麼在 2 的前面，6 的位置也不對，…
現在是區域劃分，不是排序、不是排序、不是排序！
我們換個方式來看
現在清楚了吧
我們從兩個維度來看看這個演算法的優劣，時間複雜度 O(N) ，額外空間複雜度 O(N)
時間複雜度已經沒法優化，額外空間複雜度能不能優化了？
優化實現
常規實現中，用了一個新的數組，那有沒有什麼辦法拿掉這個新數組後，仍然可以完成區域的劃分了？
我們記錄邊界索引 lte ， lte 左邊是小於等於區域， lte 至遍歷索引 i 之間是大於區域，具體實現步驟如下
分兩種情況進行處理
1、如果 arr[i] <= target ，則 arr[i] 和 lte 的前一個元素進行交換， lte 右移，i++
2、如果 arr[i] > target ， lte 不動，i++
我們看個具體案例就懂了
相當於小於等於區推著大於區往後走
再來看具體程式碼實現
此時，時間複雜度 O(N) ，只用到了一個額外變數 lte ，所以額外空間複雜度 O(1)
荷蘭國旗（三區域劃分）
我們把問題進行一個升級：給定一個整型數組 arr ，和一個數 target ，請把小於 target 的數放在數組的左邊，等於 target 的數放在數組的中間，大於 target 的數放在數組的右邊
荷蘭國旗是三種顏色
正好對應問題描述中的三個區域，所以也稱這個問題為荷蘭國旗問題
常規實現
可以在 兩區域劃分 的 常規實現 的基礎上進行改造；我們直接看程式碼
很明顯，時間複雜度 O(N) ，額外空間複雜度 O(N)
時間複雜度已經沒法優化了，我們需要優化額外空間複雜度
優化實現
如果要求額外空間複雜度 O(1)，時間複雜度 O(N)
類比 兩區域劃分 的 優化實現 ，我們分兩個邊界索引，左邊界索引 lt 往左是小於區，右邊界索引 gt 往右是大於區， lt 至遍歷索引 i 之間是等於區域，i 至 gt 之間是待定（未比較）區域
分三種情況進行處理：
1、 arr[i] < target ， arr[i] 和 lt 後一個元素進行交換， lt 右移，i++
2、 arr[i] == target ，i++
3、 arr[i] > target ， arr[i] 和 gt 前一個元素進行交換， gt 左移，i 不動
我們來看個具體案例就理解了
是不是有點感覺了？
我們再來看看程式碼的實現
時間複雜度 O(N) ，僅用了有限幾個變數，額外空間複雜度 O(1)
快速排序
配角已經悉數登場，接下來有請主角登場
1.0 版本
基於 兩區域劃分 ，我們來實現快速排序
1、我們取最後一個元素作為 target ，將最後一個元素之前（不包括最後一個元素）所有元素進行一次 兩區域劃分 ，然後將大於區的第一個元素與 target 進行交換
2、此時 target 所在的位置是 lte + 1 ，然後對 left ~ lte 和 lte+2 ~ right 這兩個區域分別做 兩區域劃分
3、重複步驟1、2，最終實現排序
直接看程式碼
2.0 版本
類似 荷蘭國旗問題 對 兩區域劃分 的優化，一次處理一批等於 target 的元素
處理步驟與 1.0 版本 類似，如下
1、取最後一個元素作為 target ，將最後一個元素之前的元素按 荷蘭國旗問題 處理，然後將大於區域的第一個元素與 target 進行交換
2、此時， lt+1 ~ gt 範圍的元素都等於 target ，不需要再處理；只需要對 left ~ lt 和 gt+1~ right 這兩個區域分別做 荷蘭國旗問題 處理
3、重複步驟1、2，最終實現排序
程式碼實現如下：
3.0 版本
不管是 1.0 版本 還是 2.0 版本 ，時間複雜度都是 O(N2)，比如對 [1,2,3,…,N-1,N] 進行排序
時間複雜度就是：O( N-1 + N-2 + … + 2 + 1 )，常數項可以忽略，也就是 O(N2)
因為我們取 target 的時候，固定取的最右邊元素，所以我們需要隨機取 target
我們可以從 left ~ right 中隨機取一個元素作為 target ，然後以此 target 對 arr[left…right] 做 荷蘭國旗問題 處理
程式碼實現如下：
partition 版本
其實就是 3.0 版本 的另外一種叫法
實現基本一致，如下
總結
演進過程
從 兩區域劃分 -> 荷蘭國旗問題 -> 快速排序
快排 1.0 -> 快排 2.0 -> 快排 3.0
遞進式實現，便於大家理解快速排序
注意點
實現的過程中，一些邊界值需要注意
邊畫圖，邊梳理，結合實際案例進行分析實現
