JS实现快速排序

基本思想

1. 确定基准数 base；

2. 分区。将小于等于 base 的放在 base 左侧，大于 base 的放在右侧；

3. 重复执行分区操作，递归终止条件为待分区数组长度为 1

JS 代码实现

/**
 * 交换元素位置
 * @param {*} arr 当前待排序数组
 * @param {*} left 左指针位置
 * @param {*} right 右指针位置
 */
function division(arr, left, right) {
  // 以最左边的数为基准
  const base = arr[left]
  while(left < right) {
    // 从序号右端开始，向左遍历，直到找到比 base 小的数
    while(left < right && arr[right] >= base){right--}
    
    // 找到比 base 小的元素，将这个元素放在对左边的位置
    arr[left] = arr[right]

    // 从序号左侧开始，向右遍历，直到找到比 base 大的数
    while(left < right && arr[left] <= base) {left++}
    // 找到比 base 大的元素，将这个元素放在最右边的位置
    arr[right] = arr[left]

  }
  // 最后放置 base 位置, 此时 left 左侧都比 base 小，右边都比 base 大
  arr[left] = base
  return left
}

/**
 * 快速排序
 * @param {*} arr 排序数组
 * @param {*} left 左指针
 * @param {*} right 右指针
 */
function quickSort(arr, left, right) {if(left >= right) return
  // 对数组进行分割，找到下次分割的基准标号
  const base = division(arr, left, right)
  // 对“基准标号”左侧进行分割
  quickSort(arr, left, base - 1)
  // 对“基准标号”右侧进行分割
  quickSort(arr, base + 1, right)

  console.log(arr)
}

算法性能

时间复杂度

当数据有序时，执行效率最差。
当数据随机分布是，效率最高。

空间复杂度

快速排序在每次分割过程中，需要 1 个空间存储基准值。而块数排序大概需要 NLog2N 次的分割处理，所以占用的空间也是 NLog2N 个。

算法稳定性

在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算方。