讲解

排序是把「无序」变成「有序」的过程，而有序是二分、双指针、贪心等一整族算法的前提——排序因此成为算法世界的入口工程。学习排序的价值不在背诵每种排序的代码（工程里永远用语言内置的 sort），而在理解几种经典策略的思想：它们分别代表了「逐步扩大有序区」「分治合并」「随机划分」三种范式。

三种 O(n²) 的简单排序各自示范一种直觉。冒泡：相邻交换把最大值一轮轮「浮」到末尾，每轮有序区加一。选择：每轮从未序区选出最小值放到已序区末尾，交换次数最少（n-1 次），适合写入成本高的场景。插入：像整理扑克牌，把新牌插入已序区的正确位置——对近乎有序的数组接近 O(n)，因此成为工程排序在小数组段的兜底策略。

O(n log n) 的两个主力。归并排序：递归拆到单元素再两两合并，合并是两个有序序列的线性归并——稳定、复杂度任何情况下都是 O(n log n)，代价是 O(n) 辅助空间；它还是「外部排序」和链表排序的首选。快速排序：选一个基准 pivot，把小于它的放左边、大于它的放右边，递归两侧——平均 O(n log n) 且常数小、原地（平均 O(log n) 栈空间），但最坏 O(n²)（已排序数组配固定 pivot），工程上用随机 pivot 规避。

「稳定性」是必须掌握的概念：相等元素排序后相对顺序不变则为稳定。它对多关键字排序至关重要（先按次要关键字排，再按主要关键字稳定排序）。归并稳定、快排不稳定、冒泡插入稳定、选择不稳定——JS 的 Array.prototype.sort 规范要求稳定，可以放心依赖。

示例

实现两个主力：归并排序（自顶向下递归版）和快速排序（Hoare 划分 + 中间值 pivot），并用确定性随机生成的 200 个元素数组与内置排序对照验证：

import assert from 'node:assert/strict';

function mergeSort(nums) {
  if (nums.length <= 1) return nums.slice();
  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));
  const merged = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // <= 保证相等元素左半先进，维持稳定性
    merged.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return merged.concat(left.slice(i), right.slice(j));
}

function quickSort(nums) {
  const arr = nums.slice();
  function partition(lo, hi) {
    const pivot = arr[(lo + hi) >> 1]; // 中间值做 pivot，规避最坏情形
    let i = lo;
    let j = hi;
    while (i <= j) {
      while (arr[i] < pivot) i++;
      while (arr[j] > pivot) j--;
      if (i <= j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
        j--;
      }
    }
    return i; // [lo, i-1] 与 [i, hi] 两侧递归
  }
  function sort(lo, hi) {
    if (lo >= hi) return;
    const idx = partition(lo, hi);
    sort(lo, idx - 1);
    sort(idx, hi);
  }
  sort(0, arr.length - 1);
  return arr;
}

// 线性同余发生器：确定性「随机」，保证每次构建结果一致
function lcg(seed) {
  let s = seed;
  return () => {
    s = (s * 48271) % 2147483647;
    return s;
  };
}

const rand = lcg(42);
const data = Array.from({ length: 200 }, () => (rand() % 1000) - 500);
const expected = data.slice().sort((a, b) => a - b);

assert.deepStrictEqual(mergeSort(data), expected);
assert.deepStrictEqual(quickSort(data), expected);
assert.deepStrictEqual(mergeSort([]), []);
assert.deepStrictEqual(quickSort([1]), [1]);
assert.deepStrictEqual(mergeSort([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5]);

console.log('200 个随机数：归并排序与快速排序结果均与内置排序一致');

注意 quickSort 里 Hoare 划分的递归边界写法（sort(lo, idx - 1) 和 sort(idx, hi)），它与 Lomuto 划分的边界不同——不同划分方案配不同边界，这也是快排「人人会背、一写就错」的原因，写完务必用含重复元素的数组验证。

常见坑

  • JS 的 sort 默认按字符串排序：[10, 9, 80].sort() 得到 [10, 80, 9]！数字排序必须传比较函数 (a, b) => a - b，这是 JS 排序的第一大坑。
  • 忘记 sort 是原地修改：排序会改变原数组；要保留原数据先 slice 一份。
  • 快排 pivot 选端点且输入已排序：退化成 O(n²) 且递归深度 n 爆栈；选中间值或随机 pivot。
  • 归并合并时错用 < 破坏稳定性：左半元素相等时先进才稳定，写 left[i] <= right[j]。
  • 以为 O(n²) 排序一无是处：插入排序在小数组和近乎有序数据上比 O(n log n) 算法更快，工程排序（TimSort 等）正是混合策略。

小结

排序三范式：逐步扩大有序区（冒泡/选择/插入）、分治合并（归并，稳定）、划分（快排，原地但不稳定）；稳定性在多关键字排序中关键；JS 的 sort 传比较函数、注意原地修改。下一章进入第一个非线性结构：二叉树与遍历。