如何利用快排的小技巧，解决算法难题？

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

今天就为大家带来面试中经常出现排序算法的深度解析。

快速排序本质上是一个前序遍历

上一篇文章中讲到，合并排序本质上和二叉树后续遍历非常类似，而快速排序本质上和二叉树的前序遍历非常类似。

首先你还先回忆一下二叉树的前序遍历：

// 递归
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;

// 根节点信息处理
array.push(root.val);

// 根节点的信息，传递给左右子树。
postOrder(root.left, array);
postOrder(root.right, array);

边界处理先不提，二叉树的前序遍历，有两个重点的特点：

• 根节点的信息；
• 根节点的信息，传递给左右子树。

简单利用伪代码表示就是：

function 前序遍历():
    获取根节点信息；
    将根节点的信息传递左右子树/左右子数组；

快速排序和前序遍历类似，这个伪代码对于快速排序同样成立。

并且对于排序算法来说，排序也就意味着有序，有序性就是信息，因此，我们要做的事情就是把能拿到的有序信息，传递给左子数组和右子数组。

有序性

那在排序算法中，如果利用有序性了？ 其实有序性的就是选择一个数 X，并且利用这个数，将数组分成三部分：

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

左右子树/子数组的处理

对于到二叉树来说，小于 X 的部分也就是二叉树的左子树，等于 X 的部分就是二叉树的根节点，大于 X 的部分就是二叉树的右子树。

二叉树对于子树的处理，就是利用递归的方式来进行处理。

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

排序算法对于子数组的处理，同样也是递归地处理左子数组和右子数组。 相对于二叉树的前序遍历来说，快速排序的左右子区间是由切分动态生成的，并不像二叉树那样由指针固定。并且对于根结点的处理，需要执行“三路切分”操作，将一个数组切分为三段；

所以总结一下，又讲回到前面的伪代码：

function 前序遍历/快速排序():
    获取根节点信息；
    将根节点的信息传递左右子树/左右子数组；

并且前序遍历/快速排序的特点可以总结为以下 3 点：

• 划分子结构
• 根节点的信息处理
• 将根节点的信息，传递给左右子树/左右子数组。

1. 划分子结构

对于二叉树而言，子树的划分是天然的，已经在数据结构里面约定好了，比如 Node.left、Node.right。

root.left
root.right 

可以直接通过树的子节点拿

但是对于数组而言，划分子结构，也就是找一个节点，将数组切分为几份，切分的时候，如果想到达最优的效率，那么将数组切为平均的两半效率应该是最高的（可以联想到二叉平衡树的效率）。但是快排不能保证选择一个数，就一定能将数组切分成为两半，所以它有自己特殊的处理。

利用 x 将数组分为三份
左子数组 = [小于 x 的部分] = [b, l)
根节点 = [等于 x 的部分] = [l, i)
右子数组 = [大于 x 的部分] = [i, e)

2. 根节点的信息处理

对于二叉树来说，根节点就是当前节点，也节点的处理也即是收集节点信息。

node
// 根节点信息处理
array.push(root.val);

而排序算法的"根节点"也就是选择的元素，并且排序算法会通过划分的子结构和选中的元素来进行排序处理也就是上面说的特殊处理；对于排序算法来说，"根节点"和划分子结构息息相关。

if (a[i] < x) {
    // 小于 x 的部分
} else if (a[i] === x) {
    // 等于 x 的部分
} else {
    // 大于 x 的部分
}

3. 将根节点的信息，传递给左右子树/左右子数组

二叉树前序遍历好说，通过递归的方式处理左右子树。

// 二叉树的前序遍历拿左右子树的信息
preOrder(root.left);
preOrder(root.right);

而排序算法需要分别对左子数组和右子数组进行排序，那么类似的对子数组的排序应该也只需要递归就可以了。

// 快速排序去拿左右子数组的信息
qsort(a, b, l);
qsort(a, i, e);

最后，不管是二叉树还是快速排序都要考虑一下边界：

二叉树的边界就是节点不能为空。

if (root === null) return null;

快速排序的边界就是：

• 当 b >= e，说明这个区间是一个空区间，没有必要再排序；
• 当 b + 1 === e，说明只有一个元素，也没有必要排序。

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);
}

这里可以思考一下，为什么我们在节点排序处理是通过 swap 操作？它和时间复杂度和空间复杂度有什么关系？

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);
    }
}

总结

通过合并排序和快速排序，可以得出结论，数组其实是另外一种形式的二叉树，只不过有时候需要我们动态地把左/右子树给切分出来，不同的切分方式，可以解决不同的问题。大家也可以自己思考和尝试，看看还能不能发现更多排序的特点和巧妙用法，并且将它们总结下来。欢迎大家一起在评论区交流。

参考

• 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