如何利用快排的小技巧，解決算法難題？
快速排序采用的是分治思想，即在一個無序的序列中選取一個任意的基準元素pivot，利用pivot將待排序的序列分成兩部分，前面部分元素均小于或等于基準元素，后面部分均大于或等于基準元素，然后采用遞歸的方法分別對前后兩部分重復上述操作，直到將無序序列排列成有序序列。
今天就為大家帶來面試中經常出現排序算法的深度解析。
快速排序本質上是一個前序遍歷
上一篇文章中講到，合并排序本質上和二叉樹后續遍歷非常類似，而快速排序本質上和二叉樹的前序遍歷非常類似。
首先你還先回憶一下二叉樹的前序遍歷：
// 遞歸
function preOrder(root, array = []) {
if (root === null) return null;
array.push(root.val);
postOrder(root.left, array);
postOrder(root.right, array);
}這里可以將代碼拆分為三部分：
// 邊界處理
if (root === null) return null;// 根節點信息處理
array.push(root.val);// 根節點的信息，傳遞給左右子樹。
postOrder(root.left, array);
postOrder(root.right, array);邊界處理先不提，二叉樹的前序遍歷，有兩個重點的特點：
- 根節點的信息；
- 根節點的信息，傳遞給左右子樹。
簡單利用偽代碼表示就是：
function 前序遍歷():
獲取根節點信息；
將根節點的信息傳遞左右子樹/左右子數組；快速排序和前序遍歷類似，這個偽代碼對于快速排序同樣成立。
并且對于排序算法來說，排序也就意味著有序，有序性就是信息，因此，我們要做的事情就是把能拿到的有序信息，傳遞給左子數組和右子數組。
有序性
那在排序算法中，如果利用有序性了？ 其實有序性的就是選擇一個數 X，并且利用這個數，將數組分成三部分：
- 小于 X 的部分；
- 等于 X 的部分；
- 大于 X 的部分；
左右子樹/子數組的處理
對于到二叉樹來說，小于 X 的部分也就是二叉樹的左子樹，等于 X 的部分就是二叉樹的根節點，大于 X 的部分就是二叉樹的右子樹。
二叉樹對于子樹的處理，就是利用遞歸的方式來進行處理。
postOrder(root.left);
postOrder(root.right);排序算法對于子數組的處理，同樣也是遞歸地處理左子數組和右子數組。 相對于二叉樹的前序遍歷來說，快速排序的左右子區間是由切分動態生成的，并不像二叉樹那樣由指針固定。并且對于根結點的處理，需要執行“三路切分”操作，將一個數組切分為三段；
所以總結一下，又講回到前面的偽代碼：
function 前序遍歷/快速排序():
獲取根節點信息；
將根節點的信息傳遞左右子樹/左右子數組；并且前序遍歷/快速排序的特點可以總結為以下 3 點：
- 劃分子結構
- 根節點的信息處理
- 將根節點的信息，傳遞給左右子樹/左右子數組。
1. 劃分子結構
對于二叉樹而言，子樹的劃分是天然的，已經在數據結構里面約定好了，比如 Node.left、Node.right。
root.left
root.right
可以直接通過樹的子節點拿但是對于數組而言，劃分子結構，也就是找一個節點，將數組切分為幾份，切分的時候，如果想到達最優的效率，那么將數組切為平均的兩半效率應該是最高的（可以聯想到二叉平衡樹的效率）。但是快排不能保證選擇一個數，就一定能將數組切分成為兩半，所以它有自己特殊的處理。
利用 x 將數組分為三份
左子數組 = [小于 x 的部分] = [b, l)
根節點 = [等于 x 的部分] = [l, i)
右子數組 = [大于 x 的部分] = [i, e)2. 根節點的信息處理
對于二叉樹來說，根節點就是當前節點，也節點的處理也即是收集節點信息。
node
// 根節點信息處理
array.push(root.val);而排序算法的"根節點"也就是選擇的元素，并且排序算法會通過劃分的子結構和選中的元素來進行排序處理也就是上面說的特殊處理；對于排序算法來說，"根節點"和劃分子結構息息相關。
if (a[i] < x) {
// 小于 x 的部分
} else if (a[i] === x) {
// 等于 x 的部分
} else {
// 大于 x 的部分
}3. 將根節點的信息，傳遞給左右子樹/左右子數組
二叉樹前序遍歷好說，通過遞歸的方式處理左右子樹。
// 二叉樹的前序遍歷拿左右子樹的信息
preOrder(root.left);
preOrder(root.right);而排序算法需要分別對左子數組和右子數組進行排序，那么類似的對子數組的排序應該也只需要遞歸就可以了。
// 快速排序去拿左右子數組的信息
qsort(a, b, l);
qsort(a, i, e);最后，不管是二叉樹還是快速排序都要考慮一下邊界：
二叉樹的邊界就是節點不能為空。
if (root === null) return null;快速排序的邊界就是：
- 當 b >= e，說明這個區間是一個空區間，沒有必要再排序；
- 當 b + 1 === e，說明只有一個元素，也沒有必要排序。
if (b > e || b + 1 >= e) {
return;
}小結
對于二叉樹來說，代碼相對比較簡單。
function preOrder(root, array = []) {
// 邊界處理
if (root === null) return null;
// 第一步：劃分子結構，二叉樹在結構上已經劃分了子結構 root.left、root.right 可以直接通過樹的子節點拿
// 第二步：根節點的信息處理
array.push(root.val)
// 第三步：將根節點的信息，傳遞給左右子樹/左右子數組（遞歸的方式）
postOrder(root.left, array);
postOrder(root.right, array);
}對于快速排序來說，如何劃分子結構？如何到達最優的效率？都是在寫算法時需要注意的。
// 交換數組中兩個元素的值
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
function qsort(a, begin, end) {
// 邊界情況
if (b > e || b + 1 >= e) {
return
}
/*********************核心代碼****************************/
// 第一步：劃分子結構
const mid = b + ((end - begin) >> 1);
// 第二步：獲取根節點信息 x
const x = a[mid];
// 根據 x 將數組一分為三 【三路切分】
let l = begin;
let i = begin;
let r = end - 1;
while(i < r) {
if (a[i] < x) {
// 小于 x 的部分
swap(a, l++, i++);
} else if (a[i] === x) {
// 等于 x 的部分
i++;
} else {
// 大于 x 的部分
swap(a, r--, i);
}
}
// 第三步：將根節點的信息傳遞左右子子樹
qsort(a, b, l);
qsort(a, i, e);
/*********************核心代碼****************************/
}
// 主函數，將數組nums排序
function quickSort(nums) {
if (nums == null)
return;
qsort(nums, 0, nums.length);
}這里可以思考一下，為什么我們在節點排序處理是通過 swap 操作？它和時間復雜度和空間復雜度有什么關系？
while(i < r) {
if (a[i] < x) {
// 小于 x 的部分
swap(a, l++, i++);
} else if (a[i] === x) {
// 等于 x 的部分
i++;
} else {
// 大于 x 的部分
swap(a, r--, i);
}
}總結
通過合并排序和快速排序，可以得出結論，數組其實是另外一種形式的二叉樹，只不過有時候需要我們動態地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。大家也可以自己思考和嘗試，看看還能不能發現更多排序的特點和巧妙用法，并且將它們總結下來。歡迎大家一起在評論區交流。
