数组基础与常用操作

排序全景

这一篇的定位

排序被拆在好几个地方讲过：归并与快排在分治那章、 堆排序在堆那章。这篇不重讲它们，只做两件事：

  1. 补上没讲过的 —— O(n²) 三兄弟、计数排序、桶排序
  2. 把十种摆到一张表里比，并回答三个「表里看不出来」的问题

⚠️ 面试里手写排序的频率其实很低（内置 sort 就够）。 真正会被问的是对比题：「快排和归并选哪个」「什么叫稳定」「能不能做到 O(n)」。 所以这篇的重心在判断依据，不在代码。

三兄弟

冒泡：相邻比较，大的往后挪

function bubbleSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let swapped = false;                      // ⭐ 这一行不是优化，是它唯一的救命稻草
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;                      // 一整趟没换过 → 已经有序
  }
  return a;
}

📌 内层的 - i 是因为每跑完一趟，最大的那个已经沉到末尾，不用再比。

插入：像理扑克牌

function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const cur = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > cur) {            // 🚨 这里是 > 不是 >=，见下文
      a[j + 1] = a[j];                        // 往后挪，腾位置
      j--;
    }
    a[j + 1] = cur;
  }
  return a;
}

⭐ 注意它不做交换，只做单向搬移 —— 一次挪一格，最后把 cur 放进空位。 比「每步都 swap」少一半的写操作。

选择：每轮挑一个最小的换到前面

function selectionSort(a) {
  for (let i = 0; i < a.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[min]) min = j;
    }
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
}

🚨 选择排序在已排好的数组上一点也不快

三兄弟都是 O(n²)，但它们对输入形态的反应完全不同。

⭐ 这里不用耗时表，用比较次数 —— 它是确定值，你跑出来会和下面一模一样 （n = 20000，「近乎有序」= 在已排序数组上随机交换 1% 对元素）：

        比较次数
        随机          已排序      近乎有序        三列之比
冒泡    199,920,249    19,999   199,718,047      9997×
插入     99,910,497    19,999     2,675,213      4996×
选择    199,990,000   199,990,000  199,990,000       1×   ← 纹丝不动

🚨 选择排序的比较次数恒等于 n(n−1)/2 = 199,990,000，与输入形态无关。 这不是「实测差不多」，是结构性事实：那个内层 for 不管数据长什么样都要 从 i+1 扫到末尾，没有任何提前退出的余地。 冒泡有 swapped、插入有 a[j] > cur 的 while 条件，它俩都能在有序数据上 退化到 n−1 次比较；选择排序结构上就没有这个位置。

📌 顺带看出两件表面上看不到的事：

  • 插入的比较次数只有冒泡的一半（9991 万 vs 1.999 亿）。冒泡每一对都要比， 插入的内层 while 一旦不满足就停。
  • 两者的移动次数完全相等：随机数据上都是 99,890,504 次 —— 这不是巧合，见下面那个恒等式。

⚠️ 耗时呢？只配写成量级

        随机        已排序     近乎有序
冒泡    几百 ms~1 s  ~0.02 ms  一两百 ms
插入    几十 ms      ~0.02 ms  一两 ms
选择    ~百 ms       ~百 ms    ~百 ms      ← 三列同档
内置    几 ms        ~0.15 ms  亚 ms

🚨 为什么连一位有效数字都不写。 三条实测理由，逐条都比「量出个数」更该记：

  1. 同一份数据、同一批参数，批与批之间就在漂。 冒泡「随机」那格， 5 批各 21 次的批中位数是 961 / 804 / 637 / 646 / 600 ms —— 漂移 1.6 倍。
  2. 换个机器负载，整张表一起缩放。 同一套代码，load 3.5 时随机那列是 646 / 48 / 103 / 2.4 ms，load 5.3 时变成 1230 / 79 / 180 / 3.6 ms —— 整体慢 50~90%。
  3. 🚨 连倍数都不稳：冒泡 ÷ 内置 sort 在前者是 269 倍、后者是 343 倍。 因为不同算法对负载的敏感度不一样，比值并不能把机器差异约掉。

⭐ 所以上面那张比较次数表才是这一节的依据。 📌 判据：报耗时之前先问「换台机器/换个时段，这个数字还剩几位可信」 —— 这里的答案是「一位都不剩，只剩量级」。

📌 顺带纠正这里以前的一句话：原来写着「近乎有序那一列每次随机打乱， 跑与跑之间会差一倍」——实测不成立。换 9 个不同的打乱种子各测一遍， 三种排序的跨种子跨度都在 1.4× 以内（机器闲时只有 1.02~1.07×）， 而不是原文说的 2×。

原因是逆序对总数被「1%」这个比例锁死了（见下面那个恒等式）， 而工作量由逆序对决定 —— 换一份打乱数据，工作量几乎没变。 ⇒ 真正会抖的不是「换一份打乱数据」，是同一份数据的重复测量 （也就是上面那三条论据说的事）。这两件事以前被混成了一句话。

🚨 所以「已经差不多排好了，随便用个简单排序吧」这个念头 —— 用插入可以（比较次数 9991 万 → 268 万，降到 1/37）， 用选择完全无效（1.9999 亿 → 1.9999 亿，一次都没少）。

⚠️ 顺带：冒泡在近乎有序时并没有快多少

看比较次数那张表的冒泡行：随机 199,920,249，近乎有序 199,718,047 —— 几乎一点没少（少了 0.1%）。而插入从 9991 万降到 268 万。

⚠️ 耗时上冒泡确实快了几倍，但那不是比较次数减少带来的， 而是交换次数从 9989 万降到 266 万 —— 少的是写操作，比较一次没省。 ⭐ 这个区分只有拆开两个计数器才看得见，耗时是把两者混在一起的。

原因是 swapped 的提前退出要求一整趟扫描一次交换都没有。 只要有一个元素离家很远，它每趟只能挪一格，就得再跑几百趟。 ⭐ 插入排序没有这个问题：它一次就把元素送到位。

📌 这也是 TimSort 选插入排序而不是冒泡当子过程的原因 —— 「对近乎有序的数据快」这个性质，只有插入排序真的具备。

⚠️ 但选择排序有一个别人没有的优点

它的交换次数最少。n = 2000 随机数据（mulberry32(20260908)、值域 0~10⁹）：

选择排序 交换   1987 次     ← 上限就是 n-1 = 1999，与数据无关
冒泡排序 交换 967141 次     ← 487 倍

📌 只有左边那个数字是硬的：200 组不同种子里选择排序的交换次数最大 1998， 从没超过 n−1。右边那个随数据变（换种子在 96~98 万之间），只该读成「约百倍量级」。

⭐ 因为选择排序每轮只在最后交换一次，扫描过程中只更新下标。 交换次数恒定在 n-1 以内，和数据无关。

📌 什么时候这有用：元素本身很大、交换代价远高于比较的时候 （比如排一个装着大对象的数组，而且不能只排指针）。 这是选择排序唯一站得住的应用场景 —— 面试里被问「选择排序还有什么用」， 答这个比答「简单」有分量。

⭐ 一个漂亮的恒等式

上面那个 967141（n=2000），其实还等于另外两个东西 —— 同一份数据上三个量分毫不差：

冒泡排序的交换次数  =  插入排序的移动次数  =  数组的逆序对数量
     967141              967141              967141

不是巧合：每一次相邻交换恰好消掉一个逆序对，而排好序意味着逆序对为零。 所以两种算法的工作量都被「输入里有多少逆序对」这一个量锁死了。

⭐ 这个恒等式的强度值得说清 —— 它不是「随机数据上碰巧相等」： 穷举 n ≤ 7、值域 0~2 的全部 3280 个数组（含大量重复值），零例外； 另外 3000 组随机数组也零例外。 📌 特意用小值域穷举，是因为相等元素是这类恒等式最容易破的地方 （相等的两个元素既不构成逆序对、也不该被交换）。

⭐ 回头看本篇第一张表就更清楚了：n=20000 随机数据上， 冒泡的交换次数与插入的移动次数都是 99,890,504 —— 而 n(n−1)/4 = 99,995,000 正是随机数组逆序对的期望值。 两个算法、两个不同名字的计数器，量到的是同一个东西。

⚠️ 顺带：这一节以前引用的是另一个规模的数字（写了「三组实测 22722 / 21454 / 23354」却没写 n）。而这三个量的大小完全由 n 决定 —— 随机数组的逆序对期望是 n(n−1)/4，那三个数其实对应 n≈300。 没有 n，那三个数读者一个都复现不出来。

📌 这个视角很有用：它解释了为什么这俩在近乎有序的数据上快 —— 不是算法变聪明了，是逆序对本来就少。 也顺带说明「用归并排序求逆序对数」那道经典题为什么成立。

🚨 > 写成 >=，插入排序就不稳定了

插入排序 while 条件里的那个比较符号，是这篇最值得记的一个细节：

while (j >= 0 && a[j] >  cur)   // ✅ 稳定
while (j >= 0 && a[j] >= cur)   // ❌ 不稳定

拿三个 key 相同的元素测：

输入                 [1a, 1b, 1c]
a[j] >  cur   →      [1a, 1b, 1c]   ✅ 保持原顺序
a[j] >= cur   →      [1c, 1b, 1a]   ❌ 完全倒过来

⚠️ 相等时不该挪。 写成 >= 的话，后来的元素会一路越过所有和它相等的元素， 排到它们前面去 —— 等值元素被整个反转。

顺带还慢：这三个元素上，> 移动 0 次，>= 移动 3 次。 一个字符同时换来「不稳定」和「更慢」。

⭐ 这和归并排序里 a[i] <= b[j] 的那个等号 是同一件事：稳定性由「相等时偏向谁」这一个决定决定。 所有稳定排序的稳定性，都落在某个比较符号的等号上。

稳定性到底影响什么

「稳定」= 值相等的元素，排完之后相对顺序不变。

只排数字时它毫无意义（两个 5 谁在前看不出来）。它在两种情况下要命：

① 排对象。 按分数排学生，两个 80 分的谁在前？不稳定的排序里， 这个顺序是随机的 —— 同样的输入、同样的代码，换个引擎结果可能不同。

② 多关键字排序。 这是稳定性真正的用武之地：

// 想要「先按部门，同部门内按入职时间」
list.sort((a, b) => a.hireDate - b.hireDate);   // 先排次要关键字
list.sort((a, b) => a.dept - b.dept);           // 再排主要关键字

⭐ 第二次排序只有稳定，第一次的结果才能被保留下来。 不稳定的话第二趟会把部门内的时间顺序打乱，两趟白排。

🚨 反过来说：如果你在用「排两趟」这个技巧，就必须确认排序是稳定的。 JS 的内置 sort 满足（下面说），手写的可不一定。

内置 sort 是稳定的吗

是。 ES2019 起规范要求 Array.prototype.sort 稳定， V8 从 7.0 起用 TimSort 实现。实测 1000 个元素、3 个不同 key，等值元素严格保序。

⚠️ 但别把这条推广到别的语言：C++ 的 std::sort 不保证稳定 （要稳定得用 std::stable_sort），Java 的 Arrays.sort 对基本类型用快排、 不稳定，对对象用 TimSort、稳定。

🚨 而且别忘了 sort() 不传比较函数会按字符串排： [10, 9, 1].sort() 得到 [1, 10, 9]。

能不能比 O(n log n) 更快

只要你的算法靠「两两比较」做决策，就不能。 这是个下界，不是「暂时没人想出来」。

论证只有两行：

  • n 个元素有 n! 种可能的排列，算法必须能区分它们
  • 每次比较只有两种结果，最多提供 1 bit 信息

所以至少需要 log₂(n!) 次比较。而 log₂(n!) ≈ n log₂ n：

n = 10     log₂(n!) ≈ 22       n·log₂n = 33
n = 100    log₂(n!) ≈ 525      n·log₂n = 664
n = 1000   log₂(n!) ≈ 8529     n·log₂n = 9966

⭐ 逃出这个下界的唯一办法是别做比较 —— 直接用元素的值去算它该放哪。 这就是下面两种。

计数排序：用值当下标

适用条件苛刻：整数、且值域不大。

function countingSort(arr, key = (x) => x) {
  const max = Math.max(...arr.map(key));
  const count = new Array(max + 1).fill(0);
  for (const x of arr) count[key(x)]++;

  for (let i = 1; i <= max; i++) count[i] += count[i - 1];   // 前缀和 → 每个值的结束位置

  const out = new Array(arr.length);
  // 🚨 必须**倒着**遍历原数组，否则不稳定
  for (let i = arr.length - 1; i >= 0; i--) out[--count[key(arr[i])]] = arr[i];
  return out;
}

⭐ 中间那步就是前缀和： count[v] 累加之后表示「值 ≤ v 的元素有几个」，也就是值为 v 的元素该放到哪结束。

🚨 那个倒序遍历

输入            [2a, 1a, 2b, 1b]
倒着填回  →     [1a, 1b, 2a, 2b]   ✅ 稳定
正着填回  →     [1b, 1a, 2b, 2a]   ❌ 等值元素倒序

因为 --count[v] 是从后往前分配位置的。倒着读原数组， 最后出现的元素先拿到最靠后的位置 —— 顺序正好对上。 正着读就反了。

⚠️ 这个错在排纯数字时完全看不出来（两个 2 长得一样）， 只有排对象、或者拿它当基数排序的子过程时才暴露 —— 而基数排序依赖计数排序的稳定性，不稳定就直接算错。

⚠️ 值域陷阱

countingSort([1, 1000000])   // 2 个元素，却要开一个长度 1000001 的数组

同样是排 2 个数，值域从 10 涨到 100 万 —— 先看确定量， 也就是 count 数组开了多长：

countingSort([1, 9])         count 数组长度        10
countingSort([1, 1000000])   count 数组长度   1000001    ← 10 万倍

⚠️ 慢在哪一目了然：全部开销都是那个百万长度数组的分配和清零， 和「排序」本身没关系。

📌 耗时只报量级就够（[1, 1000000] 约 1.6 ms，[1, 9] 和内置 sort 都在亚微秒级）。 🚨 这里以前写着三个精确耗时并由它们算出「慢 1164 倍」「慢 8000 多倍」—— 而那两端的数字连测 201 次的 max/min 相差 5 倍，比值是搭在噪声上的。 ⭐ 判据：能用确定量解释的现象，就别用耗时去证。 这里「10 万倍的数组长度」既是原因、又刚好可复现。

📌 判据：值域 k 和元素个数 n 得是同一量级，计数排序才划算 （复杂度是 O(n + k)，k 一大就全是 k 的事了）。 典型能用的场景：排年龄、排分数、排小写字母。

桶排序：分段之后各自排

把值域切成若干段，每段一个桶，桶内单独排，最后按顺序拼起来。

function bucketSort(a, n = 10) {
  const lo = Math.min(...a), hi = Math.max(...a);
  const buckets = Array.from({ length: n }, () => []);
  for (const x of a) {
    buckets[Math.min(n - 1, Math.floor((x - lo) / (hi - lo + 1e-9) * n))].push(x);
  }
  return buckets.flatMap((b) => b.sort((p, q) => p - q));
}

🚨 它的 O(n) 建立在「数据均匀分布」这个假设上，而这个假设经常不成立。 实测：5000 个数，其中 99% 挤在 [0, 0.01)，切 10 个桶：

种子 0  [4950, 10,  4,  9,  6,  5,  4,  3,  3,  6]   最大桶 99.0%
种子 4  [4967,  3,  1,  2,  3,  8,  5,  4,  3,  4]   最大桶 99.3%

⚠️ 一个桶装掉 99%，分桶这一步等于白做 —— 退化成「对整个数组排一次」。

⭐ 这里该记的是形状而不是那十个数字：换 5 个生成种子， 最大桶稳定在 98.9% ~ 99.3%，而其余九个桶都是个位数。 📌 「99% 的数据挤在一起」这个输入条件直接决定了「最大桶约 99%」—— 所以这个结论不依赖种子，而具体那十个数字依赖。

📌 所以桶排序在面试里基本只作为概念出现（「知道有基于分布的排序」）， 实战里它的适用面比计数排序还窄。

十种放在一张表里

排序 平均 最坏 空间 稳定 讲在哪 / 备注
冒泡 O(n²) O(n²) O(1) ✅ 带提前退出时，有序输入 O(n)
插入 O(n²) O(n²) O(1) ✅ ⭐ 近乎有序时接近 O(n)，小数组之王
选择 O(n²) O(n²) O(1) ❌ 交换次数最少（≤ n-1），对输入不敏感
希尔 O(n^1.3) O(n²) O(1) ❌ 分组插入排序；面试极少问
归并 O(n log n) O(n log n) O(n) ✅ 分治那章；链表排序首选
快排 O(n log n) O(n²) O(log n) ❌ 分治那章；实测常数最小
堆排序 O(n log n) O(n log n) O(1) ❌ 堆那章；唯一的原地 + 最坏 O(n log n)
计数 O(n + k) O(n + k) O(k) ✅ k = 值域；k 大就废
桶 O(n) O(n²) O(n) ✅ 依赖均匀分布
基数 O(d(n + k)) 同左 O(n + k) ✅ d = 位数；内部必须用稳定排序

⚠️ 表里最容易记反的两格：

  • 归并要 O(n) 额外空间，快排不要 —— 快排是原地分区，只有递归栈
  • 快排最坏 O(n²) —— 不是理论上的吓唬。用分治那章那个 partition（取 nums[hi]）实测， n=1000、输入已排序：比较次数 499500 次 vs 随机输入约 10800 次，46 倍。 ⭐ 左边那个数是闭式解：n(n−1)/2 —— 每次只切掉一个元素，规模只减 1。 右边随种子在 10400~11600 之间（21 个种子，跨度 1.22×），所以只写「约」。 📌 「已排序」恰恰是现实里最常见的输入形态之一。 ⚠️ 这里以前写的是「取首元素当 pivot」，而那两个数字来自取末元素的实现 —— 取首元素在已排序输入上同样退化到 499500，但随机输入是约 14700 次、比值 34 倍。 描述的实现和数字出自的实现不是同一个，这种错读者查不出来。

实际该选哪个

⭐ 绝大多数时候：用内置的。 n = 20000 随机数据实测：

                比较次数（n=20000 随机）      耗时量级
内置 sort         26 万                      几 ms
插入            9991 万   ← 384×             几十 ms
选择          1.9999 亿   ← 769×             ~百 ms
冒泡          1.9999 亿   ← 769×             几百 ms~1 s

⭐ 这里用比较次数当主轴，因为它是确定值 —— 内置 sort（TimSort）在 n=20000 随机数据上约 26 万次比较， 接近 n·log₂n = 28.6 万 的理论量级；而三兄弟都在一亿到两亿次那一档， 差整整三个数量级。

⚠️ 注意冒泡和选择的比较次数一样（都约等于 n(n−1)/2）， 但耗时差好几倍 —— 差在交换次数（冒泡近一亿次、选择不到两万次）。 📌 这也说明「比较次数」不是耗时的全部；两个计数器都要看。

内置 sort 是 TimSort：归并 + 插入的混合，小段用插入（常数小）， 还会识别数据里本来就有序的片段直接复用。手写的很难赢。

需要自己写的时候：

情况 选 为什么
数组，无特殊要求 快排 常数最小，缓存友好
需要稳定 归并 快排做不到稳定（分区时会跨越等值元素）
链表 归并 ⭐ 不需要随机访问，且省掉 O(n) 辅助数组
必须最坏 O(n log n) 且原地 堆排序 唯一同时满足这两条的
只要前 K 个 堆 / 快速选择 排全部是浪费
小整数、值域窄 计数 唯一真能突破 O(n log n) 的实用选择
n < 50 插入 常数最小；这也是 TimSort 内部的做法

🚨 注意「链表用归并」那一行：归并排序在数组上要开一个 O(n) 的辅助数组， 在链表上一个都不用开 —— 合并两条有序链表只是改指针，不复制任何节点。 （递归版仍有 O(log n) 的栈；自底向上写法能做到 O(1)。） 这是链表排序题几乎一定用归并的原因。

面试怎么答

被问到排序，按这个顺序说通常最讨巧：

  1. 先问值域：「元素是整数吗、范围多大」—— 如果窄，计数排序 O(n) 直接赢
  2. 再问约束：要稳定吗、能用额外空间吗、是链表还是数组
  3. 默认答快排，但主动补一句「最坏 O(n²)，实践中用三数取中或随机 pivot 规避」
  4. 被追问「有没有最坏也 O(n log n) 的」→ 堆排序，代价是常数大、不稳定

📌 主动说出权衡比背出复杂度值钱得多。 上面每一格的「❌」都是某个别的格子的「✅」换来的 —— 没有免费的排序。

下一步

练习

勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

  • 1051. 高度检查器简单最直白的「排一遍再逐位比」；值域只有 1~100，能用计数排序做到 O(n)
  • 1122. 数组的相对排序简单计数排序的直接应用 —— 值域 0~1000，正是「k 和 n 同量级」的场景
  • 274. H 指数中等排序 O(n log n) 能过，但引用数有上界 → 计数排序 O(n) 才是本题的正解
  • 179. 最大数中等自定义比较器；⚠️ 也是「sort() 默认按字符串排」那个坑的正面利用
  • 164. 最大间距中等桶排序的教科书题：题目明确要求 O(n)，比较排序直接出局
  • 451. 根据字符出现频率排序中等计数 + 桶；桶下标是频次，正好绕开对频次再排一次序
  • 969. 煎饼排序中等选择排序的变体 —— 每轮找最大值翻到位，交换次数同样是 O(n) 量级

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。

在本站 OJ 上练

这几道题在自己搭的判题机上，注册后直接提交，几秒出结果 —— 不用装环境、不用自己造测试数据。题目是自出的（无版权问题），每道题的数据都要求能抓出典型错解才准上线， 所以「样例过了」不等于能过。

  • P1014 从小到大排序⭐ 先用内置 sort 过一遍，再用本篇的三兄弟各手写一遍交上去 —— 结果应当完全一样