快速排序算法

分治

快速排序和寻找数组中第 K 大/小的元素，核心内容都是进行分支操作，将数据分割成比 pivot 元素小和比 pivot 元素大的两部分。

下面是升序排列的分治函数，这段代码里依次做了以下的事情：

1. 选取左指针指向的元素作为 pivot
2. 右指针从最右端开始向左移动，移动至第一个小于 pivot 的元素
3. 将右指针所指的元素移动到左指针指向的位置
4. 左指针从最左端开始向右移动，移动至第一个大于 pivot 的元素
5. 将左指针所指的元素移动到右指针指向的位置
6. 重复 2 - 5 直到左右指针相遇
7. 将左右指针相遇的位置赋值为 pivot

const partition = (nums: number[], left: number, right: number) => {
  const pivot = nums[left];
  while (left < right) {
    while (left < right && pivot <= nums[right]) {
      right--;
    }
    nums[left] = nums[right];
    while (left < right && pivot >= nums[left]) {
      left++;
    }
    nums[right] = nums[left];
  }
  nums[left] = pivot;
  return left;
}

如果是需要降序排列的结果，只需反转 pivot 与 nums[left|right] 的比较符号即可。

快速排序

递归分治即可：

const quickSort = (nums: number[]) => {
  const recurse = (left, right) => {
    if (left >= right) {
      return;
    }
    const pivotIndex = partition(left, right);
    recurse(left, pivotIndex - 1);
    recurse(pivotIndex + 1, right);
  }

  recurse(0, nums.length - 1);
  return nums;
}