排序算法6-快速排序

快速排序

• 平均时间复杂度:O(nlogn)
• 最好情况:O(nlogn)
• 最坏情况:O(n^2)
• 空间复杂度:O(logn)
• 排序方式:In-place
• 稳定性:不稳定

算法步骤:
1.从数列中挑出一个元素作为基准;
2.对数列进行分区操作，所有比基准小的摆在基准前面，所有比基准值大的摆在基准后面
3.递归地对基准的前后序列重复上面的操作

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let index = partition(arr, left, right);
    quickSort(arr, left, index - 1);
    quickSort(arr, index + 1, right);
  }
}

function partition(arr, left, right) {
  let temp;
  //默认取第一个元素即left位置作为基准值
  //index用于标记比基准值大的第一个元素的坐标
  let index = left + 1;
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[left]) {
      temp = arr[index];
      arr[index] = arr[i];
      arr[i] = temp;
      index++;
    }
  }
  //将基准值与index前一位兑换就得到基准前都是小于基准的，基准后都是大于基准的
  temp = arr[index - 1];
  arr[index - 1] = arr[left];
  arr[left] = temp;
  return index - 1;
}