快速排序

[myLightLin]

简介

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O（n²）	√
快排、归并	O（nlogn）	√
桶、计数、基数	O（n）	×

快速排序，在一组数据中，找到一个分区点 pivot，然后根据 pivot 将数据分为两半，随后递归的进行分区操作，直到区间为缩小为 1 ，数据就全部有序了。

代码

function quickSort(arr, left, right) {
  if (left >= right) return
  
  let pivot = right  // 实际选择 pivot 时应该随机一个索引
  let partitionIndex = partition(arr, pivot, left, right)
  quickSort(arr, left, partitionIndex - 1)
  quickSort(arr, partitionIndex + 1, right)
}

function partition(arr, pivot, left, right) {
  const pivotVal = arr[pivot]
  let startIndex = left
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, i, startIndex)
      startIndex++
    }
  }
  swap(arr, startIndex, pivot)
  return startIndex
}

function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

const arr = [6, 11, 3, 9, 8]
quickSort(arr, 0, arr.length - 1) // [3, 6, 8, 9, 11]

动画演示

总结

1. 时间复杂度是 O（nlogn），空间复杂度是 O（1），排序过程是不稳定的。
2. 快排利用了分治思想，它的处理是由上到下的，先划分数据，再递归的处理。
3. 它相比归并排序的优势在于，是个原地排序算法，解决了占用太大内存的问题。