快速排序

[hushicai]

快排的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quicksort(arr, left = 0, right = arr.length - 1) {
  let len = arr.length;

  if (len > 1) {
    let index = partition(arr, left, right);

    if (left < index - 1) {
      quicksort(arr, left, index - 1);
    }

    if (right > index) {
      quicksort(arr, index, right);
    }
  }

  return arr;
}

// 划分
function partition(arr, left, right) {
  let middle = Math.floor((left + right) / 2);
  let pivot = arr[middle];
  let i = left;
  let j = right;

  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }

    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }

 // 奇偶数返回不同下标，可减少中间元素
  return i === middle ? i + 1 : i;
}

// 交换
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

理解快排的基本思想，定义并实现好排序、分区、交换等不同操作，组合起来即可实现排序算法。