建站
咨詢
售后
建站咨詢
新聞中心
排序在我們的的工程應(yīng)用中無處不見，也有著非常重要的作用，比如你隨意點(diǎn)開一個(gè)搜索引擎，搜索的結(jié)構(gòu)就是經(jīng)過排序而來。各種電商網(wǎng)站的秒殺活動(dòng)，用戶點(diǎn)擊秒殺后，服務(wù)器會(huì)根據(jù)用戶的請(qǐng)求時(shí)間進(jìn)行排序。在我們的用的文檔表格中，也存在各種排序。
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對(duì)這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡(jiǎn)單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊(cè)、虛擬空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、大新網(wǎng)站維護(hù)、網(wǎng)站推廣。
所以排序真的是無處不見，因此，面試中出現(xiàn)關(guān)于排序的算法題也就不足為奇了。這篇文章通過面試中最經(jīng)常出現(xiàn)的兩種排序算法進(jìn)行深度展開。
- 合并排序
- 快速排序
本文你將收獲相應(yīng)的思想和代碼模板。
1.合并排序
合并排序本質(zhì)上與二叉樹的后序遍歷非常類似的。
// 遞歸
function postOrder(root, array = []) {
if (root === null) return null;
postOrder(root.left, array);
postOrder(root.right, array);
array.push(root.val)
}后序遍歷有個(gè)三個(gè)重要的特點(diǎn)：
- 拿到子樹的信息；
- 利用子樹的信息；
- 整合樹的信息；
這三個(gè)特點(diǎn)對(duì)應(yīng)到合并排序就是：
- 拿到子數(shù)組的信息；
- 利用子數(shù)組的信息；
- 排序出數(shù)組的信息。
利用偽代碼來表示就是：
function 后序遍歷/合并排序：
子結(jié)構(gòu)劃分
sub = 子結(jié)構(gòu)（子樹/子數(shù)組）
full = 整合（sub）這個(gè)偽代碼總結(jié)為三個(gè)關(guān)鍵點(diǎn)：
- 劃分子結(jié)構(gòu)
- 獲取子結(jié)構(gòu)的信息
- 利用子結(jié)構(gòu)的信息整合成結(jié)果
劃分子結(jié)構(gòu)
二叉樹，子樹的劃分已經(jīng)在數(shù)據(jù)結(jié)構(gòu)里面約定好了：
root.left
root.right數(shù)組，子結(jié)構(gòu)的劃分，如果想到達(dá)最優(yōu)的效率，那么將數(shù)組切為平均的兩半效率應(yīng)該是最高的。
const mid = begin + ((end - begin)>>1)
數(shù)組a = [begin, mid) => 表示左子數(shù)組
數(shù)組a = [mid, end) => 表示右子數(shù)組獲取子結(jié)構(gòu)的信息
二叉樹，獲取子樹的信息的利用就是遍歷左右子節(jié)點(diǎn)的信息。
postOrder(root.left)
postOrder(root.right)合并排序，獲取子數(shù)組的信息就是對(duì)左子數(shù)組和右子數(shù)組進(jìn)行排序。對(duì)子數(shù)組的排序，只需要遞歸就可以了。
merge(a, begin, mid)
merge(a, mid, end)利用子結(jié)構(gòu)的信息整合成結(jié)果
二叉樹，結(jié)果的合成就是將節(jié)點(diǎn)值添加到結(jié)果中。
array.push(root.val)合并排序，結(jié)果的合成，我們需要將兩個(gè)有序的子數(shù)組，合并成一個(gè)大的有序的數(shù)組。
let i = begin;
let j = mid;
let to = begin;
// 將兩個(gè)數(shù)組合并，判斷條件是，只有左右子數(shù)組中還有元素
while(i < mid || j < end) {
// 讀取左數(shù)組的元素：
// - 左數(shù)組還存在元素并且左數(shù)組的開頭元素小于右數(shù)組的開頭元素
// - 右數(shù)組沒有元素
if ((i < mid && a[i] < a[j]) || j >=end) {
// t 為臨時(shí)數(shù)組
t[to++] = a[i++];
} else {
// 讀取右數(shù)組的元素
t[to++] = a[j++];
}
}最后
最后，處理邊界：
二叉樹的邊界就是節(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é)
二叉樹，代碼如下。
function postOrder(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é)構(gòu)信息（遞歸的方式）
postOrder(root.left, array);
postOrder(root.right, array);
// 第三步：整合子結(jié)構(gòu)信息
array.push(root.val)
}合并排序，如何切分左右子數(shù)組？如何進(jìn)行合并，合并時(shí)注意循環(huán)的條件，以及穩(wěn)定排序的寫法？都是在寫算法時(shí)需要注意的。整體代碼如下：
function merge(a, t, b, e) {
// 邊界處理
if (b > e || b + 1 >= e) {
return
}
/*********************核心代碼****************************/
// 第一步：劃分子結(jié)構(gòu)
const mid = b + ((e-b)>>1);
// 第二步：獲取子結(jié)構(gòu)信息（遞歸的方式）
merge(a, t, b, mid); // 左邊子結(jié)構(gòu)
merge(a, t, mid, e); // 右邊子結(jié)構(gòu)
// 第三步：整合子結(jié)構(gòu)信息
let i = b;
let j = mid;
let to = b;
// 注意：下面是一個(gè)很重要的模板
// 將兩個(gè)數(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++];
}
}
/*********************核心代碼****************************/
// 將合并的結(jié)果拷貝到源數(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.快速排序
快速排序和合并排序一樣，可以利用二叉樹的思想來解決，合并排序本質(zhì)上與二叉樹的后序遍歷非常類似的，而快速排序本質(zhì)上與二叉樹的前序遍歷非常類似的。
前序遍歷：
// 遞歸
function preOrder(root, array = []) {
if (root === null) return null;
array.push(root.val);
postOrder(root.left, array);
postOrder(root.right, array);
}后序遍歷有個(gè)三個(gè)重要的特點(diǎn)：
- 整合樹的信息；
- 拿到子樹的信息；
- 利用子樹的信息；
這三個(gè)特點(diǎn)對(duì)應(yīng)到合并排序就是：
- 排序出數(shù)組的信息。
- 拿到子數(shù)組的信息；
- 利用子數(shù)組的信息；
利用偽代碼來表示就是：
function 前序遍歷/快速排序():
子結(jié)構(gòu)劃分
獲取根節(jié)點(diǎn)信息；
將根節(jié)點(diǎn)的信息傳遞左右子樹/左右子數(shù)組；這個(gè)偽代碼總結(jié)為三個(gè)關(guān)鍵點(diǎn)：
- 劃分子結(jié)構(gòu)
- 根節(jié)點(diǎn)的信息處理
- 將根節(jié)點(diǎn)的信息，傳遞給左右子樹/左右子數(shù)組。
劃分子結(jié)構(gòu)
二叉樹，子樹的劃分已經(jīng)在數(shù)據(jù)結(jié)構(gòu)里面約定好了：
root.left
root.right數(shù)組，子結(jié)構(gòu)的劃分，選擇一個(gè)數(shù) X，并且利用這個(gè)數(shù)，將數(shù)組分成三部分：
- 小于 X 的部分；
- 等于 X 的部分；
- 大于 X 的部分；
利用 x 將數(shù)組分為三份
左子數(shù)組 = [小于 x 的部分] = [b, l)
根節(jié)點(diǎn) = [等于 x 的部分] = [l, i)
右子數(shù)組 = [大于 x 的部分] = [i, e)根節(jié)點(diǎn)的信息處理
二叉樹，根節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)，節(jié)點(diǎn)的處理也即是收集節(jié)點(diǎn)信息。
// 根節(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 的部分
}將根節(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é)
二叉樹，代碼如下。
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);
}總結(jié)
通過合并排序和快速排序，可以得出結(jié)論，數(shù)組其實(shí)是另外一種形式的二叉樹，只不過有時(shí)候需要我們動(dòng)態(tài)地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。大家也可以自己思考和嘗試，看看還能不能發(fā)現(xiàn)更多排序的特點(diǎn)和巧妙用法，并且將它們總結(jié)下來。歡迎大家一起在評(píng)論區(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
新聞標(biāo)題：教你利用二叉樹的思想，輕松解決合并排序和快速
本文網(wǎng)址：http://www.5511xx.com/article/djpopjd.html
