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