快速排序

快排是非常高效的排序算法，其时间复杂度为 $O(n\log (n))$。

快排运用到分治的思想：

1. 找基准值（pivot）
2. 进行分区。将元素分为小于基准值、等于基准值、大于基准值三个数组。
3. 对小于、大于基准值的数组进行排序

下图为一个快排的简单例子：

基线条件

对于排序算法来说，最简单的数据就是根本不需要排序的数组：

• 空数组
• 只包含一个元素的数组

因此快排的基线条件是数组为空或只包含一个元素。因此上图中数组到元素长度为1的时候就终止分区，并且等待合并。

分区

分区其实就是找出比基准值小以及比基准值大的元素。虽然前面的例子中以第一个元素作为基准值，但其实基准值是可以取任意位置，下面则是取不同位置的元素作为基准值的分区情况：

实现

type CompareFunction<T> = (a: T, b: T) => number;
 
function quickSort<T>(array: T[], compareFn: CompareFunction<T>): T[] {
  if (array.length <= 1) {
    return array;
  }
 
  const pivotIndex = Math.floor(Math.random() * array.length);
  const pivot = array[pivotIndex];
  const equal: T[] = [];
  const lessThan: T[] = [];
  const right: T[] = [];
 
  array.forEach((item) => {
    if (compareFn(item, pivot) < 0) {
      lessThan.push(item);
    } else if (compareFn(item, pivot) > 0) {
      right.push(item);
    } else {
      equal.push(item);
    }
  });
 
  return quickSort(lessThan, compareFn).concat(equal, quickSort(right, compareFn));
}

上面的代码中，pivotIndex 通过随机数生成这个是特意这么做的，这主要是避免快排时间复杂度退化到 $O(n^2)$ 的情况。

现在假设总是将第一个元素用作基准值，且要处理的数组是有序的。由于快排不检查输入数组是否有序，因此它依然尝试对其进行排序：

由于数组并没有被分成两半，其中一个数组始终为空，因此导致调用栈非常长。如果有8个数则调用栈高度则为8。

现在回到为什么基准值的索引是随机值而不是其他数值的问题上。假设我们不是随机值，而是选取中间元素，那么我完全可以针对这个算法设计一个中间值是最小值的数组，那这个时候快排的时间复杂度又退化到 $O(n^2)$ 了。而虽然使用随机数也有可能选中最小值，但是每次递归都选中最小值的概率为 $\frac{1}{n!}$。这个概率在数据量比较大的情况下是非常小的。

进一步优化

前面的实现方式，每一次递归都需要创建新的数组并且进行合并。但是快排其实是可以直接在元素组上实现而无需创新新数组和进行合并操作的。

分区仍然是分成三部分：

• l 表示当前递归范围的开头元素索引
• r 表示当前递归范围的结束元素索引
• lt 表示小于最后一个小于基准值的索引
• gt 表示第一个大于基准值的索引
• i 表示当前正在处理的的元素的索引

循环不变量为 arr[l+1, lt] 范围中都是比基准值小的元素、arr[lt+1, i-1] == V 范围中都是与基准值相同的元素、arr[gt, r] 范围中都是比基准值大的元素。

当分区完成之后，需要将 v 的元素与 lt 索引的元素交换位置。

type CompareFunction<T> = (a: T, b: T) => number;
 
function swap<T>(arr: T[], indexA: number, indexB: number) {
  const tmp = arr[indexA];
  arr[indexA] = arr[indexB];
  arr[indexB] = tmp;
}
 
function sort<T>(arr: T[], l: number, r: number, compareFn: CompareFunction<T>) {
  if (l >= r) {
    return;
  }
 
  const pivotIndex = l + Math.floor(Math.random() * (r - l + 1));
  swap(arr, pivotIndex, l);
 
  const pivot = arr[l];
  let lt = l;
  let i = l + 1;
  let gt = r + 1;
 
  while (i < gt) {
    if (compareFn(arr[i], pivot) < 0) {
      lt++;
      swap(arr, lt, i);
      i++;
    } else if (compareFn(arr[i], pivot) > 0) {
      gt--;
      swap(arr, gt, i);
    } else {
      i++;
    }
  }
 
  swap(arr, l, lt);
 
  sort(arr, l, lt, compareFn);
  sort(arr, gt, r, compareFn);
}
 
export function quickSort<T>(array: T[], compareFn: CompareFunction<T>): T[] {
  sort(array, 0, array.length - 1, compareFn);
  return array;
}

参考资料

• 算法图解-第4章-快速排序