在这里介绍另一个重要的排序算法—快速排序。在介绍快排前，我们需要先了解一个算法思想—分治法。

分治法

分治法的字面意思是“分而治之”。把一个复杂的问题，分解成一个个容易解决的小问题来处理。这是很多算法设计的基础。
如果一个问题，可以分割成k个子问题，1 < k <= n，如果这些子问题可解，并可以利用这些子问题的解来求得原问题的解，那么这个问题就可以用分治法来解决。分治和递归往往一同出现，因为反复运用同样的方式来解决问题，和递归的理念吻合。

分治法的使用场景：

  1. 问题缩小到一定程度容易解决。
  2. 该问题可以划分成规模较小的数个子问题。
  3. 子问题的解归并后可以得到原问题的解。
  4. 每个子问题是独立的，没有重合的公共问题。

接下来我们看快速排序是如何运用分治法来解决问题的。

快速排序

快速排序的基本思路是，从数组中挑选一个数字作为基准数，把比他小的数字放到他的左边，比他大的数字放到右边，遍历完成后，这个基准数的位置index就确定了；然后再以index为界，对左右两边的数组继续进行排序，直到整个数组排序完成。
假设我们现在有以下数组 arr：

arr.png

  1. 我们以第一个数字为基准数，我们把这个数字先存到临时变量 x = 30 中。然后我们从头尾两边各设置一枚指针，i = 0, j = arr.length - 1。
  2. 先从右往左比较对应的值是否小于基准数，如果比30小，那么移动到左边。然后从左往右比较值是否大于基准数，如果是，那么移动到右边。
    1. 我们移动j，然后我们发现17 < 30 ，因此 arr[i] = 17;
    2. 然后我们移动i ，我们可以看到60 > 30, 因此 arr[j] = 60
    3. 这时我们的数组是这样的:

未命名.png

  1. 反复执行第二步，直到 i 和 j 重合，那么这个位置就是 x 的位置。

最后我们得到的数组如下：
arr2.png
30 被放在了i = 5的位置，我们发现他左边的数字都比他小，右边的数字都比他大。那么30的位置就是他的最终位置了。然后我们以i = 5 为界，对左右两边继续执行该算法。直到整个数组被排序完成，代码如下：
https://codepen.io/cauzinc/pen/ZEBxwar

  1.  /**
  2.   * @param {原数组} arr 
  3.   * @param {左边界} l 
  4.   * @param {右边界} r 
  5.   * 用数组第一个数字作为基准数，然后左右双指针
  6.   * 1. 先从右边开始移动指针，寻找比基准小的值，移动到左边
  7.   * 2. 左边开始移动指针，寻找比基准大的值，移动到右边
  8.   * 3. 直到左右指针重合，重合的位置就是基准数的位置
  9.   * 4. 以这个重合位置index为界，然后左右两边递归执行该算法，直到数组排序完成
  10.   */
  11. function quickSort (arr, l, r) {
  12.   if (l < r) {
  13.     let mid = arr[l]
  14.     let i = l
  15.     let j = r
  16.     while (i < j) {
  17.       while (i < j && arr[j] >= mid) {
  18.         j--
  19.       }
  20.       arr[i] = arr[j]
  21.       while (i < j && arr[i] < mid) {
  22.         i++
  23.       }
  24.       arr[j] = arr[i]
  25.     }
  26.     arr[i] = mid
  27.     quickSort(arr, l, i - 1)
  28.     quickSort(arr, i + 1, r)
  29.   }
  30. }

在快速排序中，我们先确定第一个数字的位置，然后剩下的两边，我们用同样的方式去确定剩下数字的位置。每次排序要解决的问题规模（数组大小）都在逐渐变小，且解决问题的方式是同样的。这样排序问题的复杂度就得到了优化。