快速排序 - wangshengliang

快速排序背后采用的也是分治的思想。

核心思想#

选择基准元素 从数组中 随机选择 一个元素作为基准值（pivot）。
分区操作 将数组中所有小于基准的元素移动到基准的左侧，大于基准的元素移动到右侧。这样，基准就处于它排序后应在的位置上。整个序列就变成了 [比基准小的值] 基准值 [比基准大的值]
递归排序 对基准左右两边的子数组分别重复上述步骤，直到所有子数组都有序。

举个例子：

假设我们有 [3, 5, 8, 1, 2, 9, 4, 7] 这个序列，这里选择 4 来作为基准值

接下来从头到尾，把小于 4 的放到左边，大于 4 的放到右边，如下图所示：

接下来对基准值左边和右边进行相同的操作即可。

好了，这是关于快速排序的最基本的思想。下面是一个快速排序整体框架的示例代码：

// 分治函数
function partition(array, left, right) {
  // todo
}

// 这是入口函数
function quickSort(array) {
  function QuickSort(array, left, right) {
    if (left < right) {
      // 该方法内部，会选择一个元素作为基准值
      // 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
      // 最后会返回基准值的索引
      let index = partition(array, left, right)
      // 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
      QuickSort(array, left, index - 1)
      QuickSort(array, index + 1, right)
    }
  }
  QuickSort(array, 0, array.length - 1)
}

const arr = [3, 5, 8, 1, 2, 9, 4, 7]
quickSort(arr)

快速排序的 partition 方法的实现有多种方式，例如：

左右指针法
挖坑法

这里我们就介绍一个最常用的左右指针法。

左右指针法#

使用左右指针法实现 partition 方法的步骤如下：

选取某个元素作为 pivot 基准值，一般取当前数组的第一个元素或者最后一个元素，这里我们采用 最后一个元素。
从 left 一直 向后寻找，直到找到一个大于 pivot 的值，然后 right 从后往前找，找到一个小于 pivot 的值，然后交换这两个元素的位置。
重复第 2 步，直到 left 和 right 相遇，这时将 pivot 放置在 left 的位置即可。

下面是一个具体的图解：

（1）原始数组，left 一开始指向第一个元素，right 一开始指向倒数第二个元素，最后一个元素是基准值

（2）left 从左往右走，走到 7 的位置就停下了，接下来 right 从右往左走，一开始在 3 的位置就停下了。然后两者进行交换

（3）left 继续往右走，走到 6 的位置停下，right 走到 0 的位置，然后停下，两者进行交换

（4）left 继续走，走到 9 停下来，right 继续走，走到 2 停下来，进行交换

（5）接下来 left 继续往右走，此时 left >= right 了，说明第一轮就走完了，将基准值和 array[left]进行交换

然后走完一轮之后，基准值左边的元素都是比基准值小的，基准值右边的元素都是比基准值大的。

代码实现#

// 分治函数
function partition(array, left, right) {
  // 首先是找一个基准值，我们取最后一个元素作为基准值
  let pivot = array[right]
  let pivotIndex = right // 基准值对应的下标
  while (left < right) {
    // 左边的left一直往右走
    while (left < right && array[left] < pivot) {
      left++
    }
    // 上面跳出 while 说明找到了一个比基准值大的
    // 右边的right一直往左边走
    while (left < right && array[right] >= pivot) {
      right--
    }
    // 上面跳出 while 说明找到了一个比基准值小的
    ;[array[left], array[right]] = [array[right], array[left]]
  }
  // 当跳出上面的while 的时候，需要将基准值和left指向的值进行交换
  ;[array[left], array[pivotIndex]] = [array[pivotIndex], array[left]]
  return left
}

// 这是入口函数
function quickSort(array) {
  function QuickSort(array, left, right) {
    // 注意下面的条件判断，是判断子数组是否还能够继续拆分
    if (left < right) {
      // 该方法内部，会选择一个元素作为基准值
      // 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
      // 最后会返回基准值的索引
      let index = partition(array, left, right)
      // 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
      QuickSort(array, left, index - 1)
      QuickSort(array, index + 1, right)
    }
  }
  QuickSort(array, 0, array.length - 1)
}

const arr = [3, 5, 8, 1, 2, 9, 4, 7]
quickSort(arr)
console.log(arr)

复杂度#

时间复杂度：O(nlogn)
空间复杂度：O(logn)

稳定性#

快排是一种 不稳定 排序，因为在分区的过程中，元素的交换可能影响相等元素的原始顺序。

-EOF-