快速排序和归并排序怎样实现？时间复杂度和稳定性有什么区别？

简答

快速排序的做法是：从数组里挑一个数当基准，把比它小的放左边、比它大的放右边，然后对左右两部分分别重复这个过程，直到每部分只剩一个数。归并排序反过来：先把数组对半拆，一直拆到每份只有一个数，再把相邻的两份按大小合并成一份有序的，一层层合并回去。

两者平均都是 O(n log n)。区别在最坏情况和稳定性。快速排序如果每次选的基准都是最大或最小值，比如对已经有序的数组总选第一个数，每次只分出一个数，就退化成 O(n²)，所以基准一般随机选或取中间位置。归并排序无论输入怎样都是 O(n log n)，但合并时需要一块额外数组，空间是 O(n)。

稳定性是说值相同的两项，排序后还保持原来的先后顺序。归并排序合并时遇到相等的值优先取左边那份，所以是稳定的；快速排序分区时会交换位置，一般不稳定。

要注意，日常开发直接用 arr.sort((a, b) => a - b)。ES2019 起规范要求 sort 是稳定的；不传比较函数时它按字符串排序，[10, 2, 1].sort() 会得到 [1, 10, 2]。

两种排序的实现

下面的实现都返回新数组，不修改输入：

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const middle = [];
  const right = [];
  for (const item of arr) {
    if (item < pivot) left.push(item);
    else if (item > pivot) right.push(item);
    else middle.push(item);
  }
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // 相等时取左边，保证稳定
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

const data = [5, 3, 8, 1, 9, 2, 3];
console.log(quickSort(data).join()); // 1,2,3,3,5,8,9
console.log(mergeSort(data).join()); // 1,2,3,3,5,8,9
console.log(data.join()); // 5,3,8,1,9,2,3

快速排序为什么要单独放一个 middle？数组里可能有很多和基准相等的值，比如全是 3。如果把相等的值也放进 left 或 right，每次递归数组都不会变小，就会无限递归。单独收进 middle，每轮至少能确定基准这一组的位置。

这个快速排序写法好懂，但每层都新建数组，空间开销大。面试中如果被要求原地排序，就改成在原数组上用两个指针交换元素来分区，空间降到 O(log n) 的递归栈。

归并排序里 left[i] <= right[j] 的等号不能去掉。去掉以后相等的值会优先取右边，原本在后面的项跑到了前面，排序就不稳定了。

稳定性在什么时候有用

表格先按姓名排好，用户再点“按部门排序”，希望同一个部门里的人仍然按姓名排列。这就要求第二次排序是稳定的：部门相同的两人，保持第一次排序后的先后顺序。因为现在 Array.prototype.sort 是稳定的，这种多次排序可以直接做。

常见追问

还有哪些排序要知道？

冒泡排序和插入排序都是 O(n²)，插入排序在数组几乎有序时很快，接近 O(n)。堆排序是 O(n log n)、原地但不稳定，前端里更常见的是用堆做优先队列，见《前端任务怎样按优先级排队？二叉堆为什么不需要每次完整排序？》。

为什么基于比较的排序不能比 O(n log n) 更快？

n 个数有 n! 种排列，每次比较只能把可能性分成两半，要确定唯一一种排列至少需要 log₂(n!) 次比较，这个量级就是 n log n。计数排序、桶排序不靠比较，在数值范围有限时可以做到线性时间。