快速排序

两处相思同淋雪，当年一别共沧桑。

快速排序

• 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤

1. 从数列中挑出一个元素，称为”基准”（pivot）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

代码实现

function quickSort(arr, start, end) {
  if (start > end) return;
  let base = arr[start];
  let left = start;
  let right = end;

  while (left < right) {
    while (left < right && arr[right] >= base) right--;
    while (left < right && arr[left] <= base) left++;
    console.log(left, right);
    if (left < right) {
      swap(arr, left, right);
    }
  }
  swap(arr, start, left);
  quickSort(arr, start, right - 1);
  quickSort(arr, right + 1, end);
  console.log(arr);
}
function swap(nums, left, right) {
  let temp = nums[left];
  nums[left] = nums[right];
  nums[right] = temp;
}