排序算法

排序是把一组数据按照某个比较规则排列。下面的实现默认按升序排序，并且都不修改输入数组。如果只要求原地排序，可以直接在输入数组上交换元素。

1. 冒泡排序

重复比较相邻元素，把较大的元素逐步交换到数组末尾。某一轮没有发生交换时，说明数组已经有序，可以提前结束。

function bubbleSort(items) {
  const result = [...items];

  for (let end = result.length - 1; end > 0; end--) {
    let swapped = false;

    for (let i = 0; i < end; i++) {
      if (result[i] > result[i + 1]) {
        [result[i], result[i + 1]] = [result[i + 1], result[i]];
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return result;
}
  • 最好时间复杂度：O(n)（已经有序且使用提前结束）；
  • 平均、最坏时间复杂度：O(n²)；
  • 额外空间复杂度：O(n)（这里的拷贝用于保护输入；原地版本为 O(1)）；
  • 稳定排序：相等元素不会交换。

2. 选择排序

每一轮从未排序区间中找到最小值，放到区间起点。它的交换次数较少，但比较次数不会因数组已有序而明显减少。

function selectionSort(items) {
  const result = [...items];

  for (let i = 0; i < result.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < result.length; j++) {
      if (result[j] < result[minIndex]) minIndex = j;
    }

    if (minIndex !== i) {
      [result[i], result[minIndex]] = [result[minIndex], result[i]];
    }
  }

  return result;
}
  • 最好、平均、最坏时间复杂度：O(n²)；
  • 额外空间复杂度：O(n)（原地版本为 O(1)）；
  • 通常不稳定：把最小值交换到前面时，可能跨过相等元素。

3. 插入排序

维护一个已经有序的前缀，每次取出下一个元素，从右向左移动较大的元素，再把它插入正确位置。数据量小或接近有序时很实用。

function insertionSort(items) {
  const result = [...items];

  for (let i = 1; i < result.length; i++) {
    const current = result[i];
    let j = i - 1;

    while (j >= 0 && result[j] > current) {
      result[j + 1] = result[j];
      j--;
    }

    result[j + 1] = current;
  }

  return result;
}
  • 最好时间复杂度：O(n)；
  • 平均、最坏时间复杂度：O(n²)；
  • 额外空间复杂度：O(n)（原地版本为 O(1)）；
  • 稳定排序：只移动严格大于当前值的元素。

4. 快速排序

选择一个基准值，将元素划分为“较小”和“较大”两部分，再递归处理子数组。下面使用双指针分区，并用随机基准降低遇到特殊输入的概率。

function quickSort(items) {
  const result = [...items];

  function partition(left, right) {
    const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
    const pivot = result[pivotIndex];
    [result[pivotIndex], result[right]] = [result[right], result[pivotIndex]];

    let storeIndex = left;
    for (let i = left; i < right; i++) {
      if (result[i] < pivot) {
        [result[i], result[storeIndex]] = [result[storeIndex], result[i]];
        storeIndex++;
      }
    }

    [result[storeIndex], result[right]] = [result[right], result[storeIndex]];
    return storeIndex;
  }

  function sort(left, right) {
    if (left >= right) return;
    const pivotIndex = partition(left, right);
    sort(left, pivotIndex - 1);
    sort(pivotIndex + 1, right);
  }

  sort(0, result.length - 1);
  return result;
}
  • 平均时间复杂度：O(n log n)；
  • 最坏时间复杂度：O(n²)（分区极不均衡）；
  • 平均额外空间复杂度：O(log n)（递归栈），最坏为 O(n)；
  • 通常不稳定；
  • 实际实现应注意递归深度、重复元素和基准值选择。

5. 归并排序

把数组不断拆成两半，分别排序后合并两个有序数组。它的时间复杂度稳定，但需要线性辅助空间。

function mergeSort(items) {
  if (items.length <= 1) return [...items];

  const middle = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, middle));
  const right = mergeSort(items.slice(middle));
  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));
}
  • 最好、平均、最坏时间复杂度：O(n log n)；
  • 额外空间复杂度：O(n)；
  • 稳定排序；
  • 适合链表排序、外部排序，以及需要保证最坏时间复杂度的场景。

6. JavaScript 内置排序

Array.prototype.sort() 会原地修改数组。比较数字时必须传入比较函数，否则元素会按字符串顺序比较：

const numbers = [10, 2, 1];
const ascending = [...numbers].sort((a, b) => a - b);
const descending = [...numbers].sort((a, b) => b - a);

比较函数返回值的含义是：负数表示 a 排在 b 前，正数表示 a 排在 b 后，0 表示两者顺序相同。现代 JavaScript 标准要求 sort 稳定，但面试中仍应先说明运行环境和比较规则。

7. 排序算法对比

算法最好时间平均时间最坏时间额外空间稳定性
冒泡排序O(n)O(n²)O(n²)O(1) 原地稳定
选择排序O(n²)O(n²)O(n²)O(1) 原地不稳定
插入排序O(n)O(n²)O(n²)O(1) 原地稳定
快速排序O(n log n)O(n log n)O(n²)O(log n) 平均不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定

这里的空间复杂度按原地版本统计；上面的示例为了不修改输入，都额外复制了数组。

8. 如何选择

  • 数据量小、基本有序：插入排序简单且通常很快；
  • 需要稳定性：选择归并排序，或使用稳定的内置排序；
  • 平均性能优先且能接受最坏情况：快速排序；
  • 需要严格的最坏 O(n log n)：归并排序；
  • 生产代码：优先使用语言内置排序，并正确传入比较函数。

9. 常见面试题

  1. 手写快速排序时如何避免最坏情况？ 随机选择基准、三数取中、三路分区，并控制递归深度。
  2. 快排和归并排序的区别？ 快排通常原地、常数较小，但最坏为 O(n²) 且不稳定；归并排序稳定、最坏为 O(n log n)，但需要 O(n) 辅助空间。
  3. 什么是稳定排序？ 如果两个元素的排序键相等，排序后仍保持它们在输入中的相对顺序。
  4. 为什么数字排序要写比较函数？ sort() 默认比较字符串，[10, 2, 1] 可能被排成 [1, 10, 2]。
  5. 如何验证排序实现？ 至少覆盖空数组、单元素、重复元素、已经有序、逆序和负数，并检查结果是否修改了输入。