快速排序基础（循环不变量）

这一节我们介绍快速排序。正如它的名字一样，快速排序是一个高效的排序算法，被应用在大多数的排序任务中，快速排序还被誉为「二十世纪最具影响力的十大算法」之一。

理解什么是划分（partition）

快速排序中最重要的思想是 划分，英文名称是 partition。我们以数组 [4, 5, 1, 6, 7, 3, 2] 为例，说明 partition 的过程。
partition 先选取一个元素作为基准元素（这个基准元素通常是随机选择的，后文会介绍原因），我们以第 1 个元素 4 为例。通过一次划分把数组分为两个部分，其中一部分 小于 基准元素 4，另一部分 大于等于 基准元素 4。此时 4 就位于了它排序以后最终在的位置，因为它前面的元素都不大于它，它后面的元素都不小于它。

接下来我们需要对 4 前面的部分和 4 后面的部分，分别执行 partition，每一次 partition 总可以排定一个元素。最终可以得到一个有序数组。

左右两边分别执行 partition 的过程是递归进行的。快速排序也使用了「分而治之」的思想。与归并排序不同的是：快速排序在「分」上面做足了功夫，每次 partition 总可以排定一个元素，因此它没有「治」（归并）的过程。

partition 的过程可能不太好记，以前我是这样记的：「大放过，小操作」，也就是说：遇到大于等于的元素就什么都不做，继续遍历，而遇到小的元素，就把它们依次交换到数组的前面去。其实这个过程更应该用「循环不变量」去理解和记忆，「循环不变量」是快速排序算法得以有效完成排序任务的依据。

循环不变量

我们定义在子区间 [left, right] 里执行 partition 的过程，
其中 pivot = nums[left]，i在一开始的时候位于 left + 1 这个位置（这是有原因的，请大家看完以后再体会）。j 的定义如下：

j 在循环循环变量 i 右移的过程中保持的不变的性质是：
在 i 向右边遍历的过程中，总有 **[left + 1, j] < pivot** 并且 **[j + 1, i) >= pivot** 成立。我们在遇到一个比基准元素 pivot小的元素，总想方设法把它放到数组的前面去，因此我们更关注小的元素。 「大放过，小操作」正是这个道理。

抓住这一点，代码编写的时候，j 的初值，以及遇到一个数如何处理，就十分清晰了，为了使得初始的时候区间 [left + 1, j] 和区间 [j + 1, i) 都为空，设置 j = left。我们可以验证一下：把j = left 代入 区间
[left + 1, j] 和区间 [j + 1, i) 得到 [left + 1, left] 与
[left + 1, left + 1) 均为空区间，符合逻辑，这一点非常重要。

在 i 向右遍历的时候，因为需要保持 j 以及 j 之前的元素都小于基准元素，因此：

1. 如果 i 指向的元素大于等于基准元素 pivot 的时候，什么都不用做；
2. 如果 i 指向的元素小于基准元素 pivot 的时候，j 先向后移动一位，再与 i 交换，然后 i 再向前移动，这就能保持在循环的过程中，i 和 j 的定义不变。

代码实现

和归并排序一样，快速排序也是通过递归实现的。我们首先写出快速排序算法的代码框架：

const sortArray = (nums) => {
  let len = nums.length;
  quickSort(nums, 0, len - 1);
  return nums;
}
const quickSort = (nums, left, right) => {
  // 注意：这里包括 > 的情况，与归并排序不同，请通过调试理解这件事情
  if (left >= right) {
      return;
  }
  /****** 前序遍历位置 ******/
  // 通过交换元素构建分界点 p
  // 经过partition， 返回的位置上的元素：
  // 左边都比它小，右边都比它大
  let p = partition(nums, left, right);
  /**********递归**********/
  quickSort(nums, left, p - 1);
  quickSort(nums, p + 1, right);
}
const partition = (nums, left, right) => {
  let pivot = nums[left];
  // 循环不变量： lt 意即 less than
  // lt所经过的元素都比 pivot小
  // [left + 1, lt] < pivot，
  // [lt + 1, i) >= pivot
  let lt = left;
  // 注意，这里取等号
  for (let i = left + 1; i <= right; i++) {
    if (nums[i] < pivot) {
      // 交换当前元素与 lt 的位置
      lt++;
      swap(nums, i, lt);
    }
  }
  // 最后这一步要记得交换到切分元素
  swap(nums, left, lt);
  return lt;
}
const swap(nums, index1, index2) {
  [nums[index1], nums[index2]] = [nums[index2], nums[index1]];
}

这一版代码提交给「力扣」第 912 题是可以得到通过的，但是这里有一个事实需要大家注意：越 有序 的数组，快速排序的消耗的时间越长，这一点跟插入排序正好相反。

快速排序的最坏时间复杂度为 O(N^2)

快速排序比一般排序算法快的原因：合适的分区，使得下一轮递归参与的元素越来越少

我们拿一个具体的例子分析，就会发现：

1. 左边有序数组，每一轮循环要把剩下的元素都看一遍，才能确定一个元素，算法在这个数组上的执行效率等同于使用选择排序
2. 而右边，一开始 4 这个元素被交换到了数组的中间，好处是：递归执行下去的时候，每一次 partition 看的元素更少了，递归树更低，因此可以较快地完成排序任务；
3. 事实上，以后我们对于树的优化，总是想方设法让树的高度更低，让树更「平衡」，这样执行效率更高；
4. 一个比较容易想到的方案就是在一开始的时候，随机 选择一个元素交换到待排序部分的开头。

   let pivot = arr[Math.floor(Math.random() * (right - left + 1)) + left]

但是即使随机选择了 pivot 元素，每一次也有可能选到最极端的那个元素，变成上面那幅图左边的样子。事实上，这种「运气很差」的事情发生的概率很低，最坏情况出现的概率为：

这个数值是很小的。因此通常意义下，加了随机选择 pivot 元素的快速排序，在平均意义下的递归树是「接近平衡」的，时间复杂度和归并排序一样。完整代码如下：

const sortArray = (nums) => {
  let len = nums.length;
  quickSort(nums, 0, len - 1);
  return nums;
}
const quickSort = (nums, left, right) => {
  // 注意：这里包括 > 的情况，与归并排序不同，请通过调试理解这件事情
  if (left >= right) {
      return;
  }
  /****** 前序遍历位置 ******/
  // 通过交换元素构建分界点 p
  // 经过partition， 返回的位置上的元素：
  // 左边都比它小，右边都比它大
  // 如果没有随机选择，对于有序数组
  // partition 每次都返回第一个元素
  // quickSort就会递归太多次
  let p = partition(nums, left, right);
  /**********递归**********/
  quickSort(nums, left, p - 1);
  quickSort(nums, p + 1, right);
}
const partition = (nums, left, right) => {
  // 随机选择一个元素作为切分元素
  let pivot = arr[Math.floor(Math.random() * (right - left + 1)) + left];
  // 循环不变量： lt 意即 less than
  // [left + 1, lt] < pivot，
  // [lt + 1, i) >= pivot
  let lt = left;
  // 注意，这里取等号
  for (let i = left + 1; i <= right; i++) {
    // 慢指针捕捉比pivot小的元素
    if (nums[i] < pivot) {
      // 交换当前元素与 lt 的位置
      lt++;
      swap(nums, i, lt);
    }
  }
  // 最后这一步要记得交换到切分元素
  swap(nums, left, lt);
  return lt;
}
const swap(nums, index1, index2) {
  [nums[index1], nums[index2]] = [nums[index2], nums[index1]];
}

时间复杂度与空间复杂度

这里我们所说的快速排序是增加了「随机选择切分元素」版本的快速排序。根据上一节的分析，快速排序的时间复杂度是 O(NlogN)，这里 N 是输入数组的长度。理解这件事情可以从「归并排序」的时间复杂度分析着手，我们之前说过，「快速排序」与「归并排序」的不同之处是：「归并排序」在「分」这件事情上没有做什么事情，所以需要有「合」的步骤，而「快速排序」正好相反。

由于快速排序使用了递归函数，递归调用栈的深度我们认为接近 logN，因此空间复杂度是 O(logN) （不计算输入数组的长度）。

这里大家看到了，快速排序虽然是原地排序，但它需要借助额外的空间用于辅助递归函数的执行。这一点说明了：原地排序与空间复杂度 O(1) 其实是不同的概念。

总结

这一章我们学习了归并排序，我们接着把这张表填完。

练习

1. 查阅资料，使用「三数取中法」选择 partition 过程的切分元素；

2. 自行编写测试用例，完成下面的实验：

   在输入数据接近有序时，没有实现「随机选择切分元素」的快速排序比归并排序慢很多

3. 完成「力扣」第 215 题：数组中的第 K 个最大元素（中等）

说明：这是著名的 top K 问题，注意这道题基准元素 pivot 一定需随机化

1. 完成「力扣」第 26 题：删除排序数组中的重复项（简单）

说明：通过这道问题练习「循环不变量」

1. 完成「力扣」第 80 题：删除排序数组中的重复项 II（中等）

「随机选择切分元素」的优化在有一种情况下是失效的，即输入数组有大量重复元素的时候，这个时候递归树的高度依然不平衡。这就要用到我们马上要介绍的优化方法：指针对撞的快速排序。我们将在下一节介绍，感谢大家。