排序算法

快速排序

基本思想：

1. 找到一个基准值，将数组分成两个部分，左边的都比基准值小，右边的都比基准值大。

   基准值一般选用第一个数，然后与最后一个数开始比较

2. 左右两个部分又可以进行上述过程，直到左右两个部分都只有一个元素。

可以看出将排序过程采用了分治思想，将问题分解成更小的子问题，然后递归求解，最后合并结果。

function quickSort(arr, start = 0, end = arr.length - 1) {
  if (start < end) {
    const base = arr[start]; // 基准值
    let left = start,
      right = end;
    while (left < right) {
      while (left < right && base <= arr[right]) {
        right--;
      }
      arr[left] = arr[right];
      while (left < right && base >= arr[left]) {
        left++;
      }
      arr[right] = arr[left];
    }
    arr[left] = base;
    quickSort(arr, start, left - 1); // 分治
    quickSort(arr, left + 1, end); // 分治
  }
}

特性

• 不稳定
• 原地排序
• 平均时间复杂度：O(nlogn)；平均空间复杂度：O(logn)

归并排序

基本思想：

1. 分：将组数分成两个子数组，直到不能再分。
2. 治：将两个子数组合并成一个有序数组。创建一个新数组，再分别为两个子数组设置标志位同向双指针移动比较，将较小的值放入新数组中。

典型分治思想。

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let l = 0,
    r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
      result.push(left[l++]);
    } else {
      result.push(right[r++]);
    }
  }
  result.push(...left.slice(l), ...right.slice(r));
  return result;
}

特性

• 稳定
• “治”时需要额外的数组空间，并且最终也返回这个数组（非原地排序）
• 平均时间复杂度：O(nlogn)；平均空间复杂度：O(n)