算法思想

利用“分治”的思想，选择一个哨兵数字，将原先的数据分为两部分（大于哨兵和小于哨兵）。
重复这个过程，直到不能为止

时间复杂度

在最好的情况下，假设 为排序的时间，那么有：

那么就可以推导出


那么在最差的情况下呢

就退化成了

实现代码

function quickSort(nums, begin, end) {
  if (begin < end) {
    let q = partition(nums, begin, end);
    quickSort(nums, begin, q - 1);
    quickSort(nums, q + 1, end);
  }
}
function partition(nums, begin, end) {
  let pivot = Math.floor(Math.random() * (end - begin)) + begin;
  swap(nums, pivot, end);
  let j = begin - 1;
  for (let i = begin; i < end; ++i) {
    if (nums[i] < nums[end]) {
      j++;
      swap(nums, i, j);
    }
  }
  swap(nums, j + 1, end);
  return j + 1;
}
function swap(nums, a, b) {
  let t = nums[a]; nums[a] = nums[b]; nums[b] = t;
}

变种：快速选择

查找数组内的第 K 大数：先选择一个哨兵，然后将数组分为两部分，根据返回 q 的位置：

• q = k，那么返回 q
• q < k，那么继续分右边
• q > k，那么继续分左边