二叉树前置思想

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。(听说高手都是这么想的) 所以先打点基础吧。

快排算法思路

代码框架

const sort = function (nums, lo, hi) {
  if (lo >= hi) {
    return;
  }
  // 对 nums[lo..hi] 进行切分
  // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
  let p = partition(nums, lo, hi);
  // 去左右子数组进行切分
  sort(nums, lo, p - 1);
  sort(nums, p + 1, hi);
};

对比二叉树前序遍历

// 二叉树遍历框架
const traverse = function (root) {
  if (root === null) {
    return;
  }
  // ***** 前序位置 *****
  console.log(root.val);
  // *******************
  traverse(root.left);
  traverse(root.right);
};

一句话总结快速排序：快速排序是先将一个元素排好序，然后再将剩下的元素排好序。

快速排序的核心无疑是 partition 函数， partition 函数的作用是在 nums[lo..hi] 中寻找一个切分点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]

一个元素左边的元素都比它小，右边的元素都比它大，所以 partition 函数干的事情，其实就是把 nums[p] 这个元素排好序了。

从二叉树的视角，我们可以把子数组 nums[lo..hi] 理解成二叉树节点上的值，sort 函数理解成二叉树的遍历函数。

partition 函数每次都将数组切分成左小右大两部分，恰好和二叉搜索树左小右大的特性吻合。

欸☝️🤓，那快速排序的过程可不就是是一个构造二叉搜索树的过程。

但是二叉搜索树不平衡的极端情况，需要引入随机性，比如洗牌算法。当然这种东西就不是现在的我能碰瓷的了，随便记一下就好了。

快速排序代码实现

const quickSort = function (nums) {
  // 排序整个数组（原地修改）
  sort(nums, 0, nums.length - 1);
};

const sort = function (nums, lo, hi) {
  if (lo >= hi) {
    return;
  }
  // 对 nums[lo..hi] 进行切分
  // 使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
  let p = partition(nums, lo, hi);
  sort(nums, lo, p - 1);
  sort(nums, p + 1, hi);
};

// 对 nums[lo..hi] 进行切分
const partition = function (nums, lo, hi) {
  let pivot = nums[lo];
  // 关于区间的边界控制需格外小心，稍有不慎就会出错
  // 这里把 i, j 定义为开区间，同时定义：
  // [lo, i) <= pivot；(j, hi] > pivot
  // [lo, i) <= pivot; (j, hi] > pivot
  // 之后都要正确维护这个边界区间的定义
  let i = lo + 1,
    j = hi;
  // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
  while (i <= j) {
    while (i < hi && nums[i] <= pivot) {
      i++;
      // 此 while 结束时恰好 nums[i] > pivot
    }
    while (j > lo && nums[j] > pivot) {
      j--;
      // 此 while 结束时恰好 nums[j] <= pivot
    }

    if (i >= j) {
      break;
    }
    // 此时 [lo, i) <= pivot && (j, hi] > pivot
    // 交换 nums[j] 和 nums[i]
    [nums[i], nums[j]] = [nums[j], nums[i]];
    // 此时 [lo, i] <= pivot && [j, hi] > pivot
  }
  // 最后将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
  [nums[lo], nums[j]] = [nums[j], nums[lo]];
  return j;
};