快速排序

[sl1673495]

初始版

最初的版本，对于 partition 这一步中的取基准值，我们直接取最左边的值，然后把小于这个值的划分在它的左边，把大于等于这个值的划分在它右边，然后分别对左和右再进一步做递归的快速排序。

它的问题在于，如果数组是个近似有序的数组的话，它的时间复杂度会退化到接近 On² 的级别。排序分治形成的二叉树会非常不平衡，退化成接近链表。

function partition(arr, left, right) {
  // 取一个基准值 取第一项
  let pivot = arr[left]

  // arr[left+1...index] < pivot, arr[index+1...i) > pivot
  let index = left
  for (let i = left + 1; i <= right; i++) {
    let num = arr[i]
    if (num < pivot) {
      swap(arr, index + 1, i)
      index++
    }
  }

  swap(arr, left, index)
  return index
}

随机数优化版

对于上述的近似有序数组的问题，我们可以选择每次的基准值选取一个随机值，这样退化成 On² 的可能性就趋近于零了。

function partition(arr, left, right) {
  // 取一个基准值 取随机值
  let rand = random(left, right)
  swap(arr, left, rand)
  let pivot = arr[left]

  // arr[left+1...index] < pivot, arr[index+1...i) > pivot
  let index = left
  for (let i = left + 1; i <= right; i++) {
    let num = arr[i]
    if (num < pivot) {
      // 如果当前值小于基准值的话，就交换到index + 1的位置去。
      // 扩充了index的范围 [index...], pivot, [...right]
      swap(arr, index + 1, i)
      index++
    }
  }

  swap(arr, left, index)
  return index
}

但是这样还是会有问题，对于重复元素很多的数组，只会简单的把大于等于基准值的元素简单粗暴的划分到右侧范围里，然后继续递归的快排，浪费了大量时间。
比如 [8, 9, 9, 9, 9, 9, 9, 10]，下一步只会拿掉左边的 [8]，进一步的去排 [9, 9, 9, 9, 9, 9, 10]，然后很有可能又只是拿出了一个 9，继续递归… 排序树依然很不平衡。

三路快排

最终优化版就是三路快排了，顾名思义这种快排就是把数组区分成 < v, ===v, >v 三个区间，然后把等于 v 的区间排除掉，继续对剩余的两个区间进行递归的快速排序。

function sortArray(arr) {
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

/**
 * 对 arr[l...r] 部分进行快速排序
 * @param {number[]} arr
 * @param {number} l 左边界
 * @param {number} r 右边界
 */
function _quickSort(arr, l, r) {
  if (l >= r) {
    return
  }
  let [p, q] = partition(arr, l, r)
  _quickSort(arr, l, p)
  _quickSort(arr, q, r)
}
function random(low, high) {
  return Math.round(Math.random() * (high - low)) + low
}
function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

/**
 * 对 arr[l...r] 部分进行快速排序
 * @param {number[]} arr
 * @param {number} l 左边界
 * @param {number} r 右边界
 * @returns {number} 返回索引值p，使得arr[l...p-1] < arr[p] < arr[p+1...r]
 */
function partition(arr, left, right) {
  // 取一个基准值 取随机值
  let rand = random(left, right)
  swap(arr, left, rand)
  let pivot = arr[left]

  // 三路 注意看注释里的区间
  let lt = left // arr[left + 1...lt] < v
  let gt = right + 1 // arr[gt...r] > v
  let index = left + 1 // arr[lt + 1...index) === v

  while (index < gt) {
    let num = arr[index]
    if (num < pivot) {
      swap(arr, index, lt + 1)
      lt++
      index++
    } else if (num > pivot) {
      swap(arr, index, gt - 1)
      gt--
    } else if (num === pivot) {
      index++
    }
  }
  swap(arr, left, lt)

  return [lt - 1, gt]
}