快排算法实现

[jerryyxu]

排序思路（从小到大）：

• 选择一个基准数（pivot），进行排序，分区（partition）
• 让基准数左边分区的数都小于基准数，右分区的数值都大于基准数，获得该基准数索引
• 对基准数左右分区进行重复上述步骤进行排序，直到分区长度小于 1

function quickSort(arr) {
  return partition2(arr, 0, arr.length);
}

function partition(arr, low, high) {
  const pivot = low;
  let index = pivot + 1;

  for (let i = index; i <= high; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }

  index--;
  swap(arr, pivot, index);

  return index;
}

function swap(arr, i, j) {
  i !== j && ([arr[i], arr[j]] = [arr[j], arr[i]]);
}

function partition2(arr, low, high) {
  if (low < high) {
    const pivot = partition(arr, low, high);

    partition2(arr, low, pivot - 1);
    partition2(arr, pivot + 1, high);
  }

  return arr;
}

[jerryyxu]

快速排序是不稳定的排序算法，平均时间复杂度为 O(nlogn) ，最好情况下为 O(nlogn)，最差情况下为 O(n^2)。另外，快速排序算法实现上还是递归的方式，在无法实现尾递归优化的情况下还是存在调用栈溢出的可能，因此不能进行大量数据的排序。