blog

Quick Sort

2020.05.24

原理

以给定值为基准将数组进行分区，左侧区域全都小于等于基准值，右侧区域全都大于基准值。

步骤

  1. 标记当前范围首尾，i为首、j为尾；以首值为基准值x
  2. 从后往前找到一个小于或等于x的值，与x做交换
  3. 从前往后找到一个大于x的值，与x交换
  4. 重复2、3步骤直至i等于j

这样一次得到的结果为x基准值右侧全都大于基准值，x左侧全都小于等于基准值

实现

function swap (array, i, j) {
  array[i] = array[i] + array[j];
  array[j] = array[i] - array[j];
  array[i] = array[i] - array[j];
}

function quickSort (array, start, end) {
  if (start >= end) {
    // 越界终止
    return array;
  }
  const x = array[start]; // 基准
  let i = start, j = end;
  // 左侧 <= 基准值 < 右侧
  while (i < j) {
    while (i < j && x < array[j]) {
      // 从后往前找到比x小的数
      j--;
    }
    i !== j && swap(array, i, j);
    while (i < j && array[i] <= x) {
      // 从前往后找到比x大的数
      i++;
    }
    i !== j && swap(array, i, j);
  }
  quickSort(array, start, i - 1);
  quickSort(array, i + 1, end);
  return array;
}

const array = [21, 32, 43, 98, 54, 45, 23, 4, 66, 86];

quickSort(array, 0, array.length - 1);
console.log(array);