快速排序

快速排序也许是最常用的排序算法了。它的时间复杂度为 O(nlog(n))，且性能通常比其他复杂度为 O(nlog(n)) 的排序算法要好。和归并排序一样，快速排序也使用分而治之的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开）。

算法步骤

1. 首先，从数组中选择一个值作为主元（pivot），也就是数组中间的那个值。
2. 创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分（partition）操作。
3. 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。

代码实现

// 主函数
function quickSort(nums) {
  return quick(nums, 0, nums.length - 1);
}

// 递归函数
function quick(nums, left, right) {
  let index;

  if (nums.length > 1) {
    index = partition(nums, left, right);

    if (left < index - 1) {
      quick(nums, left, index - 1);
    }
    if (index < right) {
      quick(nums, index, right);
    }
  }

  return nums;
}

// 划分过程
function partition(nums, left, right) {
  // 首先从数组中选择一个值作为主元 pivot，通常是数组中间的那个值
  const pivotIndex = Math.floor((left + right) / 2);
  const pivot = nums[pivotIndex];
  let i = left;
  let j = right;

  while (i <= j) {
    // 移动左指针，直到找到一个比 pivot 大的值
    while (nums[i] < pivot) i++;
    // 移动右指针，直到找到一个比 pivot 小的值
    while (nums[j] > pivot) j--;
    // 如果 i <= j，交换两个指针对应的值
    if (i <= j) {
      swap(nums, i, j);
      i++;
      j--;
    }
  }

  return i;
}

复杂度分析

时间复杂度：快速排序的时间复杂度是 O(nlog(n))，但性能通常比其他复杂度为 O(nlog(n)) 的排序算法要好。

归并排序与快速排序的区别：快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

/* 快速排序模板 */
function sort(nums, lo, hi) {
  const p = partition(nums, lo, hi);
  sort(nums, lo, p - 1);
  sort(nums, p, hi);
}

/* 归并排序模板 */
function sort(nums, lo, hi) {
  const mid = (lo + hi) / 2;
  const left = sort(nums, lo, mid);
  const right = sort(nums, mid + 1, hi);
  // 合并两个有序数组
  merge(left, right);
}