快速排序采用的是分治思想，即在一個(gè)無(wú)序的序列中選取一個(gè)任意的基準(zhǔn)元素pivot，利用pivot將待排序的序列分成兩部分，前面部分元素均小于或等于基準(zhǔn)元素，后面部分均大于或等于基準(zhǔn)元素，然后采用遞歸的方法分別對(duì)前后兩部分重復(fù)上述操作，直到將無(wú)序序列排列成有序序列。

今天就為大家?guī)?lái)面試中經(jīng)常出現(xiàn)排序算法的深度解析。

快速排序本質(zhì)上是一個(gè)前序遍歷

上一篇文章中講到，合并排序本質(zhì)上和二叉樹(shù)后續(xù)遍歷非常類似，而快速排序本質(zhì)上和二叉樹(shù)的前序遍歷非常類似。

首先你還先回憶一下二叉樹(shù)的前序遍歷：

// 遞歸
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)的信息，傳遞給左右子樹(shù)。
postOrder(root.left, array);
postOrder(root.right, array);

邊界處理先不提，二叉樹(shù)的前序遍歷，有兩個(gè)重點(diǎn)的特點(diǎn)：

• 根節(jié)點(diǎn)的信息；
• 根節(jié)點(diǎn)的信息，傳遞給左右子樹(shù)。

簡(jiǎn)單利用偽代碼表示就是：

function 前序遍歷():
    獲取根節(jié)點(diǎn)信息；
    將根節(jié)點(diǎn)的信息傳遞左右子樹(shù)/左右子數(shù)組；

快速排序和前序遍歷類似，這個(gè)偽代碼對(duì)于快速排序同樣成立。

并且對(duì)于排序算法來(lái)說(shuō)，排序也就意味著有序，有序性就是信息，因此，我們要做的事情就是把能拿到的有序信息，傳遞給左子數(shù)組和右子數(shù)組。

有序性

那在排序算法中，如果利用有序性了？ 其實(shí)有序性的就是選擇一個(gè)數(shù) X，并且利用這個(gè)數(shù)，將數(shù)組分成三部分：

• 小于 X 的部分；
• 等于 X 的部分；
• 大于 X 的部分；

左右子樹(shù)/子數(shù)組的處理

對(duì)于到二叉樹(shù)來(lái)說(shuō)，小于 X 的部分也就是二叉樹(shù)的左子樹(shù)，等于 X 的部分就是二叉樹(shù)的根節(jié)點(diǎn)，大于 X 的部分就是二叉樹(shù)的右子樹(shù)。

二叉樹(shù)對(duì)于子樹(shù)的處理，就是利用遞歸的方式來(lái)進(jìn)行處理。

postOrder(root.left);
postOrder(root.right);

排序算法對(duì)于子數(shù)組的處理，同樣也是遞歸地處理左子數(shù)組和右子數(shù)組。 相對(duì)于二叉樹(shù)的前序遍歷來(lái)說(shuō)，快速排序的左右子區(qū)間是由切分動(dòng)態(tài)生成的，并不像二叉樹(shù)那樣由指針固定。并且對(duì)于根結(jié)點(diǎn)的處理，需要執(zhí)行“三路切分”操作，將一個(gè)數(shù)組切分為三段；

所以總結(jié)一下，又講回到前面的偽代碼：

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

并且前序遍歷/快速排序的特點(diǎn)可以總結(jié)為以下 3 點(diǎn)：

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

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

對(duì)于二叉樹(shù)而言，子樹(shù)的劃分是天然的，已經(jīng)在數(shù)據(jù)結(jié)構(gòu)里面約定好了，比如 Node.left、Node.right。

root.left
root.right 

可以直接通過(guò)樹(shù)的子節(jié)點(diǎn)拿

但是對(duì)于數(shù)組而言，劃分子結(jié)構(gòu)，也就是找一個(gè)節(jié)點(diǎn)，將數(shù)組切分為幾份，切分的時(shí)候，如果想到達(dá)最優(yōu)的效率，那么將數(shù)組切為平均的兩半效率應(yīng)該是最高的（可以聯(lián)想到二叉平衡樹(shù)的效率）。但是快排不能保證選擇一個(gè)數(shù)，就一定能將數(shù)組切分成為兩半，所以它有自己特殊的處理。

利用 x 將數(shù)組分為三份
左子數(shù)組 = [小于 x 的部分] = [b, l)
根節(jié)點(diǎn) = [等于 x 的部分] = [l, i)
右子數(shù)組 = [大于 x 的部分] = [i, e)

2. 根節(jié)點(diǎn)的信息處理

對(duì)于二叉樹(shù)來(lái)說(shuō)，根節(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ì)通過(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 的部分
}

3. 將根節(jié)點(diǎn)的信息，傳遞給左右子樹(shù)/左右子數(shù)組

二叉樹(shù)前序遍歷好說(shuō)，通過(guò)遞歸的方式處理左右子樹(shù)。

// 二叉樹(shù)的前序遍歷拿左右子樹(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);

最后，不管是二叉樹(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é)

對(duì)于二叉樹(shù)來(lái)說(shuō)，代碼相對(duì)比較簡(jiǎn)單。

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)的效率？都是在寫算法時(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);
}

這里可以思考一下，為什么我們?cè)诠?jié)點(diǎn)排序處理是通過(guò) 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é)

通過(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ū)交流。

參考

• 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