教你利用二叉樹的思想，輕松解決合并排序和快速
排序在我們的的工程應用中無處不見，也有著非常重要的作用，比如你隨意點開一個搜索引擎，搜索的結構就是經(jīng)過排序而來。各種電商網(wǎng)站的秒殺活動，用戶點擊秒殺后，服務器會根據(jù)用戶的請求時間進行排序。在我們的用的文檔表格中，也存在各種排序。
所以排序真的是無處不見，因此，面試中出現(xiàn)關于排序的算法題也就不足為奇了。這篇文章通過面試中最經(jīng)常出現(xiàn)的兩種排序算法進行深度展開。
- 合并排序
- 快速排序
本文你將收獲相應的思想和代碼模板。
1.合并排序
合并排序本質上與二叉樹的后序遍歷非常類似的。
// 遞歸
function postOrder(root, array = []) {
if (root === null) return null;
postOrder(root.left, array);
postOrder(root.right, array);
array.push(root.val)
}后序遍歷有個三個重要的特點：
- 拿到子樹的信息；
- 利用子樹的信息；
- 整合樹的信息；
這三個特點對應到合并排序就是：
- 拿到子數(shù)組的信息；
- 利用子數(shù)組的信息；
- 排序出數(shù)組的信息。
利用偽代碼來表示就是：
function 后序遍歷/合并排序：
子結構劃分
sub = 子結構（子樹/子數(shù)組）
full = 整合（sub）這個偽代碼總結為三個關鍵點：
- 劃分子結構
- 獲取子結構的信息
- 利用子結構的信息整合成結果
劃分子結構
二叉樹，子樹的劃分已經(jīng)在數(shù)據(jù)結構里面約定好了：
root.left
root.right數(shù)組，子結構的劃分，如果想到達最優(yōu)的效率，那么將數(shù)組切為平均的兩半效率應該是最高的。
const mid = begin + ((end - begin)>>1)
數(shù)組a = [begin, mid) => 表示左子數(shù)組
數(shù)組a = [mid, end) => 表示右子數(shù)組獲取子結構的信息
二叉樹，獲取子樹的信息的利用就是遍歷左右子節(jié)點的信息。
postOrder(root.left)
postOrder(root.right)合并排序，獲取子數(shù)組的信息就是對左子數(shù)組和右子數(shù)組進行排序。對子數(shù)組的排序，只需要遞歸就可以了。
merge(a, begin, mid)
merge(a, mid, end)利用子結構的信息整合成結果
二叉樹，結果的合成就是將節(jié)點值添加到結果中。
array.push(root.val)合并排序，結果的合成，我們需要將兩個有序的子數(shù)組，合并成一個大的有序的數(shù)組。
let i = begin;
let j = mid;
let to = begin;
// 將兩個數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < end) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=end) {
// t 為臨時數(shù)組
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}最后
最后，處理邊界：
二叉樹的邊界就是節(jié)點不能為空。
if (root === null) return null;合并排序的邊界就是：
- 當 b >= e，說明這個區(qū)間是一個空區(qū)間，沒有必要再排序；
- 當 b + 1 === e，說明只有一個元素，也沒有必要排序。
if (b > e || b + 1 >= e) {
return
}小結
二叉樹，代碼如下。
function postOrder(root, array = []) {
// 邊界處理
if (root === null) return null;
// 第一步：劃分子結構，二叉樹在結構上已經(jīng)劃分了子結構 root.left、root.right 可以直接通過樹的子節(jié)點拿
// 第二步：獲取子結構信息（遞歸的方式）
postOrder(root.left, array);
postOrder(root.right, array);
// 第三步：整合子結構信息
array.push(root.val)
}合并排序，如何切分左右子數(shù)組？如何進行合并，合并時注意循環(huán)的條件，以及穩(wěn)定排序的寫法？都是在寫算法時需要注意的。整體代碼如下：
function merge(a, t, b, e) {
// 邊界處理
if (b > e || b + 1 >= e) {
return
}
/*********************核心代碼****************************/
// 第一步：劃分子結構
const mid = b + ((e-b)>>1);
// 第二步：獲取子結構信息（遞歸的方式）
merge(a, t, b, mid); // 左邊子結構
merge(a, t, mid, e); // 右邊子結構
// 第三步：整合子結構信息
let i = b;
let j = mid;
let to = b;
// 注意：下面是一個很重要的模板????????????
// 將兩個數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < e) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=e) {
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}
/*********************核心代碼****************************/
// 將合并的結果拷貝到源數(shù)組中
for (let i = b; i < e; i++) {
a[i] = t[i];
}
}
function mergeSort(nums) {
if (nums === null || nums.length === 0) {
return;
}
merge(nums, [], 0, nums.length)
return nums;
}2.快速排序
快速排序和合并排序一樣，可以利用二叉樹的思想來解決，合并排序本質上與二叉樹的后序遍歷非常類似的，而快速排序本質上與二叉樹的前序遍歷非常類似的。
前序遍歷：
// 遞歸
function preOrder(root, array = []) {
if (root === null) return null;
array.push(root.val);
postOrder(root.left, array);
postOrder(root.right, array);
}后序遍歷有個三個重要的特點：
- 整合樹的信息；
- 拿到子樹的信息；
- 利用子樹的信息；
這三個特點對應到合并排序就是：
- 排序出數(shù)組的信息。
- 拿到子數(shù)組的信息；
- 利用子數(shù)組的信息；
利用偽代碼來表示就是：
function 前序遍歷/快速排序():
子結構劃分
獲取根節(jié)點信息；
將根節(jié)點的信息傳遞左右子樹/左右子數(shù)組；這個偽代碼總結為三個關鍵點：
- 劃分子結構
- 根節(jié)點的信息處理
- 將根節(jié)點的信息，傳遞給左右子樹/左右子數(shù)組。
劃分子結構
二叉樹，子樹的劃分已經(jīng)在數(shù)據(jù)結構里面約定好了：
root.left
root.right數(shù)組，子結構的劃分，選擇一個數(shù) X，并且利用這個數(shù)，將數(shù)組分成三部分：
- 小于 X 的部分；
- 等于 X 的部分；
- 大于 X 的部分；
利用 x 將數(shù)組分為三份
左子數(shù)組 = [小于 x 的部分] = [b, l)
根節(jié)點 = [等于 x 的部分] = [l, i)
右子數(shù)組 = [大于 x 的部分] = [i, e)根節(jié)點的信息處理
二叉樹，根節(jié)點就是當前節(jié)點，節(jié)點的處理也即是收集節(jié)點信息。
// 根節(jié)點信息處理
array.push(root.val);排序算法的"根節(jié)點"也就是選擇的元素，并且排序算法會通過劃分的子結構和選中的元素來進行排序處理也就是上面說的特殊處理；對于排序算法來說，"根節(jié)點"和劃分子結構息息相關。
if (a[i] < x) {
// 小于 x 的部分
} else if (a[i] === x) {
// 等于 x 的部分
} else {
// 大于 x 的部分
}將根節(jié)點的信息，傳遞給左右子樹/左右子數(shù)組
二叉樹，通過遞歸的方式處理左右子樹。
// 二叉樹的前序遍歷拿左右子樹的信息
preOrder(root.left);
preOrder(root.right);而排序算法需要分別對左子數(shù)組和右子數(shù)組進行排序，那么類似的對子數(shù)組的排序應該也只需要遞歸就可以了。
// 快速排序去拿左右子數(shù)組的信息
qsort(a, b, l);
qsort(a, i, e);最后
最后，不管是二叉樹還是快速排序都要考慮一下邊界：
二叉樹的邊界就是節(jié)點不能為空。
if (root === null) return null;快速排序的邊界就是：
- 當 b >= e，說明這個區(qū)間是一個空區(qū)間，沒有必要再排序；
- 當 b + 1 === e，說明只有一個元素，也沒有必要排序。
if (b > e || b + 1 >= e) {
return;
}小結
二叉樹，代碼如下。
function preOrder(root, array = []) {
// 邊界處理
if (root === null) return null;
// 第一步：劃分子結構，二叉樹在結構上已經(jīng)劃分了子結構 root.left、root.right 可以直接通過樹的子節(jié)點拿
// 第二步：根節(jié)點的信息處理
array.push(root.val)
// 第三步：將根節(jié)點的信息，傳遞給左右子樹/左右子數(shù)組（遞歸的方式）
postOrder(root.left, array);
postOrder(root.right, array);
}對于快速排序來說，如何劃分子結構？如何到達最優(yōu)的效率？都是在寫算法時需要注意的。整體代碼如下：
// 交換數(shù)組中兩個元素的值
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);
// 第二步：獲取根節(jié)點信息 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é)點的信息傳遞左右子子樹
qsort(a, b, l);
qsort(a, i, e);
/*********************核心代碼****************************/
}
// 主函數(shù)，將數(shù)組nums排序
function quickSort(nums) {
if (nums == null)
return;
qsort(nums, 0, nums.length);
}總結
通過合并排序和快速排序，可以得出結論，數(shù)組其實是另外一種形式的二叉樹，只不過有時候需要我們動態(tài)地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。大家也可以自己思考和嘗試，看看還能不能發(fā)現(xiàn)更多排序的特點和巧妙用法，并且將它們總結下來。歡迎大家一起在評論區(qū)交流。
參考
- https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
- https://kaiwu.lagou.com/course/courseInfo.htm?courseId=685#/detail/pc?id=6697
- https://juejin.cn/post/7286307632193273915
- https://juejin.cn/post/7287914116296458275
- https://juejin.cn/post/7287473826060304445
