教你利用二叉樹(shù)的思想，輕松解決合并排序和快速

作者：不愛(ài)吃貓的魚(yú)er 2023-10-30 15:01:00

通過(guò)合并排序和快速排序，可以得出結(jié)論，數(shù)組其實(shí)是另外一種形式的二叉樹(shù)，只不過(guò)有時(shí)候需要我們動(dòng)態(tài)地把左/右子樹(shù)給切分出來(lái)，不同的切分方式，可以解決不同的問(wèn)題。

排序在我們的的工程應(yīng)用中無(wú)處不見(jiàn)，也有著非常重要的作用，比如你隨意點(diǎn)開(kāi)一個(gè)搜索引擎，搜索的結(jié)構(gòu)就是經(jīng)過(guò)排序而來(lái)。各種電商網(wǎng)站的秒殺活動(dòng)，用戶(hù)點(diǎn)擊秒殺后，服務(wù)器會(huì)根據(jù)用戶(hù)的請(qǐng)求時(shí)間進(jìn)行排序。在我們的用的文檔表格中，也存在各種排序。

所以排序真的是無(wú)處不見(jiàn)，因此，面試中出現(xiàn)關(guān)于排序的算法題也就不足為奇了。這篇文章通過(guò)面試中最經(jīng)常出現(xiàn)的兩種排序算法進(jìn)行深度展開(kāi)。

合并排序
快速排序

本文你將收獲相應(yīng)的思想和代碼模板。

1.合并排序

合并排序本質(zhì)上與二叉樹(shù)的后序遍歷非常類(lèi)似的。

// 遞歸
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)：

拿到子樹(shù)的信息；
利用子樹(shù)的信息；
整合樹(shù)的信息；

這三個(gè)特點(diǎn)對(duì)應(yīng)到合并排序就是：

拿到子數(shù)組的信息；
利用子數(shù)組的信息；
排序出數(shù)組的信息。

利用偽代碼來(lái)表示就是：

function 后序遍歷/合并排序：
    子結(jié)構(gòu)劃分
    sub = 子結(jié)構(gòu)（子樹(shù)/子數(shù)組）
    full = 整合（sub）

這個(gè)偽代碼總結(jié)為三個(gè)關(guān)鍵點(diǎn)：

劃分子結(jié)構(gòu)
獲取子結(jié)構(gòu)的信息
利用子結(jié)構(gòu)的信息整合成結(jié)果

劃分子結(jié)構(gòu)

二叉樹(shù)，子樹(shù)的劃分已經(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)的信息

二叉樹(shù)，獲取子樹(shù)的信息的利用就是遍歷左右子節(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é)果

二叉樹(shù)，結(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ù)組的開(kāi)頭元素小于右數(shù)組的開(kāi)頭元素
  //    - 右數(shù)組沒(méi)有元素
  if ((i < mid && a[i] < a[j]) || j >=end) {
    // t 為臨時(shí)數(shù)組
    t[to++] = a[i++];
  } else {
  // 讀取右數(shù)組的元素
    t[to++] = a[j++];  
  }
}

最后

最后，處理邊界：

二叉樹(shù)的邊界就是節(jié)點(diǎn)不能為空。

if (root === null) return null;

合并排序的邊界就是：

當(dāng) b >= e，說(shuō)明這個(gè)區(qū)間是一個(gè)空區(qū)間，沒(méi)有必要再排序；
當(dāng) b + 1 === e，說(shuō)明只有一個(gè)元素，也沒(méi)有必要排序。

if (b > e || b + 1 >= e) {
  return 
}

小結(jié)

二叉樹(shù)，代碼如下。

function postOrder(root, array = []) {
  // 邊界處理
  if (root === null) return null;
  // 第一步：劃分子結(jié)構(gòu)，二叉樹(shù)在結(jié)構(gòu)上已經(jīng)劃分了子結(jié)構(gòu) root.left、root.right 可以直接通過(guò)樹(shù)的子節(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)定排序的寫(xiě)法？都是在寫(xiě)算法時(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ù)組的開(kāi)頭元素小于右數(shù)組的開(kāi)頭元素
    //    - 右數(shù)組沒(méi)有元素
   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.快速排序

快速排序和合并排序一樣，可以利用二叉樹(shù)的思想來(lái)解決，合并排序本質(zhì)上與二叉樹(shù)的后序遍歷非常類(lèi)似的，而快速排序本質(zhì)上與二叉樹(shù)的前序遍歷非常類(lèi)似的。

前序遍歷：

// 遞歸
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)：

整合樹(shù)的信息；
拿到子樹(shù)的信息；
利用子樹(shù)的信息；

這三個(gè)特點(diǎn)對(duì)應(yīng)到合并排序就是：

排序出數(shù)組的信息。
拿到子數(shù)組的信息；
利用子數(shù)組的信息；

利用偽代碼來(lái)表示就是：

function 前序遍歷/快速排序():
    子結(jié)構(gòu)劃分
    獲取根節(jié)點(diǎn)信息；
    將根節(jié)點(diǎn)的信息傳遞左右子樹(shù)/左右子數(shù)組；

這個(gè)偽代碼總結(jié)為三個(gè)關(guān)鍵點(diǎn)：

劃分子結(jié)構(gòu)
根節(jié)點(diǎn)的信息處理
將根節(jié)點(diǎn)的信息，傳遞給左右子樹(shù)/左右子數(shù)組。

劃分子結(jié)構(gòu)

二叉樹(shù)，子樹(shù)的劃分已經(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)的信息處理

二叉樹(shù)，根節(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ì)通過(guò)劃分的子結(jié)構(gòu)和選中的元素來(lái)進(jìn)行排序處理也就是上面說(shuō)的特殊處理；對(duì)于排序算法來(lái)說(shuō)，"根節(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ù)/左右子數(shù)組

二叉樹(shù)，通過(guò)遞歸的方式處理左右子樹(shù)。

// 二叉樹(shù)的前序遍歷拿左右子樹(shù)的信息
preOrder(root.left);
preOrder(root.right);

而排序算法需要分別對(duì)左子數(shù)組和右子數(shù)組進(jìn)行排序，那么類(lèi)似的對(duì)子數(shù)組的排序應(yīng)該也只需要遞歸就可以了。

// 快速排序去拿左右子數(shù)組的信息
qsort(a, b, l);
qsort(a, i, e);

最后

最后，不管是二叉樹(shù)還是快速排序都要考慮一下邊界：

二叉樹(shù)的邊界就是節(jié)點(diǎn)不能為空。

if (root === null) return null;

快速排序的邊界就是：

當(dāng) b >= e，說(shuō)明這個(gè)區(qū)間是一個(gè)空區(qū)間，沒(méi)有必要再排序；
當(dāng) b + 1 === e，說(shuō)明只有一個(gè)元素，也沒(méi)有必要排序。

if (b > e || b + 1 >= e) {
  return;
}

小結(jié)

二叉樹(shù)，代碼如下。

function preOrder(root, array = []) {
  // 邊界處理
  if (root === null) return null;
  // 第一步：劃分子結(jié)構(gòu)，二叉樹(shù)在結(jié)構(gòu)上已經(jīng)劃分了子結(jié)構(gòu) root.left、root.right 可以直接通過(guò)樹(shù)的子節(jié)點(diǎn)拿
  // 第二步：根節(jié)點(diǎn)的信息處理
  array.push(root.val)
  // 第三步：將根節(jié)點(diǎn)的信息，傳遞給左右子樹(shù)/左右子數(shù)組（遞歸的方式）
  postOrder(root.left, array);
  postOrder(root.right, array);
}

對(duì)于快速排序來(lái)說(shuō)，如何劃分子結(jié)構(gòu)？如何到達(dá)最優(yōu)的效率？都是在寫(xiě)算法時(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)的信息傳遞左右子子樹(shù)
 qsort(a, b, l);
 qsort(a, i, e);
 /*********************核心代碼****************************/
}
// 主函數(shù)，將數(shù)組nums排序 
function quickSort(nums) {
  if (nums == null)
    return;
  qsort(nums, 0, nums.length);
}

總結(jié)

通過(guò)合并排序和快速排序，可以得出結(jié)論，數(shù)組其實(shí)是另外一種形式的二叉樹(shù)，只不過(guò)有時(shí)候需要我們動(dòng)態(tài)地把左/右子樹(shù)給切分出來(lái)，不同的切分方式，可以解決不同的問(wèn)題。大家也可以自己思考和嘗試，看看還能不能發(fā)現(xiàn)更多排序的特點(diǎn)和巧妙用法，并且將它們總結(jié)下來(lái)。歡迎大家一起在評(píng)論區(qū)交流。