鴻蒙OS 4.0公測機型公布：甚至連nova6都支持
華為全新的HarmonyOS 4.0操作系統將于今天下午正式登場，官方在發布會之前也已經正式給出了可升級的機型產品，這意味著這些機型會率先支持升級享用。這次的HarmonyOS 4.0支持
排序在我們的的工程應用中無處不見，也有著非常重要的作用，比如你隨意點開一個搜索引擎，搜索的結構就是經過排序而來。各種電商網站的秒殺活動，用戶點擊秒殺后，服務器會根據用戶的請求時間進行排序。在我們的用的文檔表格中，也存在各種排序。
所以排序真的是無處不見，因此，面試中出現關于排序的算法題也就不足為奇了。這篇文章通過面試中最經常出現的兩種排序算法進行深度展開。
本文你將收獲相應的思想和代碼模板。
合并排序本質上與二叉樹的后序遍歷非常類似的。
// 遞歸function postOrder(root, array = []) { if (root === null) return null; postOrder(root.left, array); postOrder(root.right, array); array.push(root.val)}后序遍歷有個三個重要的特點：
這三個特點對應到合并排序就是：
利用偽代碼來表示就是：
function 后序遍歷/合并排序： 子結構劃分 sub = 子結構（子樹/子數組） full = 整合（sub）這個偽代碼總結為三個關鍵點：
二叉樹，子樹的劃分已經在數據結構里面約定好了：
root.leftroot.right數組，子結構的劃分，如果想到達最優的效率，那么將數組切為平均的兩半效率應該是最高的。
const mid = begin + ((end - begin)>>1)數組a = [begin, mid) => 表示左子數組數組a = [mid, end) => 表示右子數組二叉樹，獲取子樹的信息的利用就是遍歷左右子節點的信息。
postOrder(root.left)postOrder(root.right)合并排序，獲取子數組的信息就是對左子數組和右子數組進行排序。對子數組的排序，只需要遞歸就可以了。
merge(a, begin, mid)merge(a, mid, end)二叉樹，結果的合成就是將節點值添加到結果中。
array.push(root.val)合并排序，結果的合成，我們需要將兩個有序的子數組，合并成一個大的有序的數組。
let i = begin;let j = mid;let to = begin;// 將兩個數組合并，判斷條件是，只有左右子數組中還有元素while(i < mid || j < end) { // 讀取左數組的元素： // - 左數組還存在元素并且左數組的開頭元素小于右數組的開頭元素 // - 右數組沒有元素 if ((i < mid && a[i] < a[j]) || j >=end) { // t 為臨時數組 t[to++] = a[i++]; } else { // 讀取右數組的元素 t[to++] = a[j++]; }}最后，處理邊界：
二叉樹的邊界就是節點不能為空。
if (root === null) return null;合并排序的邊界就是：
if (b > e || b + 1 >= e) { return }二叉樹，代碼如下。
function postOrder(root, array = []) { // 邊界處理 if (root === null) return null; // 第一步：劃分子結構，二叉樹在結構上已經劃分了子結構 root.left、root.right 可以直接通過樹的子節點拿 // 第二步：獲取子結構信息（遞歸的方式） postOrder(root.left, array); postOrder(root.right, array); // 第三步：整合子結構信息 array.push(root.val)}合并排序，如何切分左右子數組？如何進行合并，合并時注意循環的條件，以及穩定排序的寫法？都是在寫算法時需要注意的。整體代碼如下：
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; // 注意：下面是一個很重要的模板???????????? // 將兩個數組合并，判斷條件是，只有左右子數組中還有元素 while(i < mid || j < e) { // 讀取左數組的元素： // - 左數組還存在元素并且左數組的開頭元素小于右數組的開頭元素 // - 右數組沒有元素 if ((i < mid && a[i] < a[j]) || j >=e) { t[to++] = a[i++]; } else { // 讀取右數組的元素 t[to++] = a[j++]; } } /*********************核心代碼****************************/ // 將合并的結果拷貝到源數組中 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;}快速排序和合并排序一樣，可以利用二叉樹的思想來解決，合并排序本質上與二叉樹的后序遍歷非常類似的，而快速排序本質上與二叉樹的前序遍歷非常類似的。
前序遍歷：
// 遞歸function preOrder(root, array = []) { if (root === null) return null; array.push(root.val); postOrder(root.left, array); postOrder(root.right, array);}后序遍歷有個三個重要的特點：
這三個特點對應到合并排序就是：
利用偽代碼來表示就是：
function 前序遍歷/快速排序(): 子結構劃分 獲取根節點信息； 將根節點的信息傳遞左右子樹/左右子數組；這個偽代碼總結為三個關鍵點：
二叉樹，子樹的劃分已經在數據結構里面約定好了：
root.leftroot.right數組，子結構的劃分，選擇一個數 X，并且利用這個數，將數組分成三部分：
利用 x 將數組分為三份左子數組 = [小于 x 的部分] = [b, l)根節點 = [等于 x 的部分] = [l, i)右子數組 = [大于 x 的部分] = [i, e)二叉樹，根節點就是當前節點，節點的處理也即是收集節點信息。
// 根節點信息處理array.push(root.val);排序算法的"根節點"也就是選擇的元素，并且排序算法會通過劃分的子結構和選中的元素來進行排序處理也就是上面說的特殊處理；對于排序算法來說，"根節點"和劃分子結構息息相關。
if (a[i] < x) { // 小于 x 的部分} else if (a[i] === x) { // 等于 x 的部分} else { // 大于 x 的部分}二叉樹，通過遞歸的方式處理左右子樹。
// 二叉樹的前序遍歷拿左右子樹的信息preOrder(root.left);preOrder(root.right);而排序算法需要分別對左子數組和右子數組進行排序，那么類似的對子數組的排序應該也只需要遞歸就可以了。
// 快速排序去拿左右子數組的信息qsort(a, b, l);qsort(a, i, e);最后，不管是二叉樹還是快速排序都要考慮一下邊界：
二叉樹的邊界就是節點不能為空。
if (root === null) return null;快速排序的邊界就是：
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);}通過合并排序和快速排序，可以得出結論，數組其實是另外一種形式的二叉樹，只不過有時候需要我們動態地把左/右子樹給切分出來，不同的切分方式，可以解決不同的問題。大家也可以自己思考和嘗試，看看還能不能發現更多排序的特點和巧妙用法，并且將它們總結下來。歡迎大家一起在評論區交流。
本文鏈接：http://www.tebozhan.com/showinfo-26-15858-0.html教你利用二叉樹的思想，輕松解決合并排序和快速
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 可以提取圖像文本的五大 Python 庫
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號