5. 快速排序

算法描述

快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将数据分割成两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，是整个数据变成有序序列。

如何将数据分割成两个部分，就需要着一个基准数，把小于基准数的都放到基准数的左边，把大于基准数的都放到基准数右边。为了方便，一般把数组的第一个元素当作基准数。

动图实现

这个图里是用数组中最后一个值当作基准值。

算法实现

快速排序中，最关键的地方在于寻找基准值所在的目标位置。先把小于基准值的都交换到基准值身后，最后将基准值和交换的最后一个值交换，这样基准值前面都是小于基准值的数，基准值后面都是大于基准值的数。

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  let partitionIndex = 0
  if (left < right) {
    partitionIndex = partition(arr, left, right)
    quickSort(arr, left, partitionIndex - 1)
    quickSort(arr, partitionIndex + 1, right)
  }
  return arr
}
const partition = (arr, left, right) => {
  let index = left + 1
  for (let i = index; i <= right; i++) {
    if (arr[left] > arr[i]) {
      swap(arr, i, index)
      index++
    }
  }
  swap(arr, left, index - 1)
  return index - 1
}
const swap = (arr, i, j) => {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}