编程语言研究书库
JavaScript 数据结构与算法

第 6 章 排序 — 从 O(n²) 到 O(n),比较与不比的两条路线

第 6 章 排序 — 从 O(n²) 到 O(n),比较与不比的两条路线

这一章讲什么: 怎么把一堆乱序的记录排成有序。它是全书最长的算法章: 十种正经排序 + 五种故意低效的,外加排序问题的六个分类维度。 它在全书链条里的位置: 算法主菜。第 5 章的分治、贪心、稳定性的概念 在这里全部变成具体代码;第 14 章还会回来讲堆排序,与第 10 章的基数排序实现 一起补完这张图。

1. 顶层全景

  排序 = 重排记录,使键非降序,且输出是输入的一个排列(不许丢元素!)
      │
      ├─ 比较排序(通用,任何可比的键)
      │    O(n²):冒泡 → 鸡尾酒 → 选择 → 插入     (简单,小数组可用)
      │    改进:  梳排序 / 希尔排序               (跳跃缩小,希尔约 O(n^1.5))
      │    O(n log n):快排(平均,最坏 O(n²)) / 归并(稳定,要额外空间)
      │    下界:任何比较排序 ≥ O(n log n)          (信息论论证)
      │
      └─ 不比较排序(键必须满足额外条件)
           位图排序 O(n):键范围小、无重复、纯数字
           计数排序 O(n):允许重复
           基数排序 O(n):逐位分桶,最古老(打孔卡),要稳定性兜底

  图说:左支通用但撞下界,右支突破下界但钥匙受限。选型先看键,再看 n。

2. 主线例子:[22, 9, 60, 12, 4, 56] 走四个代表性算法

用原书的标准演示数组,走四个台阶,每步旁边有具体状态:

第 ① 步:冒泡排序(比较排序的地板)。 相邻比较、逆序就换,每趟把当前 最大值「冒」到右端:22,9 换 → 9,22,60 不换 → 60,12 换 → 60,4 换 → 60,56 换,第一趟结束 [9, 22, 12, 4, 56, 60],60 到位。 共 5+4+3+2+1 = 15 次比较,O(n²) 的来历清清楚楚1。 一个实用增强(习题 6.7):每趟记 swaps,一趟无交换就提前收工—— 近乎有序的数组几乎免费2。

第 ② 步:插入排序(小数组之王)。 像理扑克牌:前 i 张已有序,第 i+1 张 从右往左插到位。走查:第一张 22 独成一段;插 9 → [9, 22];插 60 → 原位; 插 12 → [9, 12, 22, 60];插 4 → 一路换到头;插 56 → [9, 12, 22, 56, 60] 完成。 平均也是 O(n²),但近乎有序的输入接近 O(n),这让它是「混合排序」 里小分段的标配3。

第 ③ 步:快速排序(分治旗舰)。 选最右为 pivot,一趟划分把小的换左边: 数组 [22, 9, 60, 12, 4, 56],pivot=56,扫一遍把小于 56 的都换到左侧, 56 落到位置 4;递归排 [22, 9, 12, 4] 与 [60] 即完成。 平均 O(n log n);已排序的输入是它的死穴——每次划分只缩一格,退化 O(n²)4。 三个增强:随机选 pivot / 三值取中(median of three)防有序输入; 小区间切插入排序(CUTOFF=7);双 pivot 分三段(Java 原生数组排序就是它)5。

第 ④ 步:计数排序(不比较的样板)。 允许重复的数字键、范围可估时用。 先数次数再算落点:[22, 9, 60, 12, 4, 56] 的计数表(以 4 为 0 号)中, 键 4、9、12、22、56、60 各 1 次;落点表从 0 累加:4→0、9→1、12→2、22→3、56→4、60→5; 再按落点把每个值写回原数组。两次扫描都是 O(n),总 O(n)——但前提是键范围不大, 否则计数表本身爆掉6。

3. 核心原理

3.1 先立规矩:排序问题的六个分类维度

动笔前先把问题本身说清,书里给了六个维度7:

  1. 定义:排序 = 按键非降序重新排列,且输出必须是输入的一个排列(元素一个不多一个不少)。 书里的反面教材:const wrongWayToSort = (inputData) => [];——返回空数组 也算「有序」,所以「不丢元素」必须写进定义8。
  2. 内部 vs 外部排序:全装得进内存是内部排序(本章全部);装不下要分段 落盘再归并是外部排序——「真到那一步,用系统的 sort 工具」9。
  3. 原地性(in-place):是否需要与输入规模成正比的额外空间? 快排的递归栈 O(log n) 算原地;归并要 O(n) 辅助数组,不算10。
  4. 在线 vs 离线:数据流式到来边收边排(在线,如插入排序)还是全到齐再排 (离线,通常更快)。在线算法被迫像贪心一样做「可能后悔」的决定11。
  5. 稳定性(stable):键相等的元素,排完后的相对顺序是否与输入一致? 重要场景:先按名字排、再按「是否星标」排,第二次排序若稳定,名字序就保住 (书里的 Joliet/Romeo 例子)12。 任何排序都能强行变稳:把键扩成「原键 + 原下标」,排完丢掉下标13。
  6. 自适应性(adaptive):能否利用输入里已有的有序部分(希尔是,快排近乎反自适应)14。

还有第七件事:JavaScript 自带的 .sort()。不传比较函数时按字符串字典序排—— [22, 9, 60].sort() 得到 [22, 60, 9](9 被当成 "9"),数字排序必须传 (a, b) => a - b15。ES2019 起规范要求 .sort() 稳定; 新出的 .toSorted() 不改原数组(呼应第 2 章的纯度纪律)。 书里态度务实:「多数情况下用 JavaScript 自己的 sort 可能最有效」16。

3.2 比较排序的下界:O(n log n) 是撞不破的墙

为什么所有比较排序都停在 O(n log n)?书里的论证只用了一个类比: 二十个问题游戏——20 个是非题能从 100 万个可能中锁定目标(2²⁰ = 1,048,576)。 排序也一样:n 个元素有 n! 种排列,每次比较回答一个「是/非」, 要区分 n! 种可能就得问 log₂(n!) 次;由斯特林公式,n! 长得像 nⁿ, 所以 log(n!) = O(n log n)17。 推论两条:比较排序再好也到不了 O(n);但如果放弃比较(利用键本身的值), 下界作废——位图/计数/基数就是后门。这个「比较 vs 不比较」的分界 是本章最重要的概念,选型时第一个要问。

3.3 O(n²) 一族:简单、稳定(部分)、好懂

冒泡、鸡尾酒(shuttle,左右往返)、选择、插入,四个都 O(n²),差别在常数与性格:

算法一趟干什么性格
冒泡大值逐格右冒写好懂;加交换检查后有适应性
鸡尾酒左冒一趟、右沉一趟常数约快一倍;乌龟兔子双向都照顾
选择找最小换到前面交换次数最少(至多 n−1 次),适合写代价高的介质
插入新元素插进有序段近乎有序时近 O(n);小数组最快

「兔子与乌龟」的比喻来自梳排序:大值在数组前部(兔子)一趟就蹿到尾, 小值在尾部(乌龟)每次只能挪一格。梳排序先把间距拉大(除以 1.3), 兔子乌龟都大步跳,间距收到 1 退回冒泡——最坏仍 O(n²) 但实测好得多18。 希尔排序把同样思想用在插入排序上:先按大间距(4)把数组变成 4 条短有序序列, 再间距 2、最后间距 1——末趟插入面对的已经近乎有序,代价大减。 书里用 Knuth 序列(1, 4, 13, 40, …, 3k+1),复杂度约 O(n^1.5)19。

3.4 快排的三个增强:工程化的完整样本

快排平均 O(n log n)、最坏 O(n²)、原地,但「工程版」还要修三件事:

  1. pivot 选择:固定取最右在已排序输入上必死。解 A:随机取(平摊掉坏输入); 解 B:三值取中——左、中、右三个元素排序后的中位数;更狠的「ninther」 (三段各自三值取中,再取中)是常用库的做法20。
  2. 小区间切换:分段短于 CUTOFF(如 7)就换插入排序——递归开销不值当21。
  3. 双 pivot / 三路划分:两个 pivot 把数组切三段(小于/之间/大于); 重复键多时优势大。习题 6.10 的三路版(荷兰国旗问题)让等于 pivot 的 元素整块免排——重复键是快排隐藏的性能杀手22。

归并排序站在快排对面:稳定、保证 O(n log n) 最坏,代价是 O(n) 额外空间 和复制开销。书末点出 TimSort(归并+插入+利用已有有序段的混合体)是 Java、JavaScript(V8)的实际排序实现,「我们学过的所有零件都在里面」23。

3.5 不比较三兄弟:用键的值换 O(n)

  • 位图排序:布尔数组当下标用,扫一遍置位、按位输出——O(n), 但三条硬限制:纯数字、范围小、无重复(重复直接抛错)24。
  • 计数排序:位图的计数版,计数表 + 落点表两步,允许重复, 还能扩展成键+数据(把数据跟着落点搬)。依然是 O(n),依然要求范围可控6。
  • 基数排序:最古老(赫尔瑞斯打孔卡,IBM 源头),逐位分桶: 先按个位分 10 桶收回,再按十位……每趟必须是稳定排序,否则高位白排 (回链稳定性一节)。O(n×位数),键值范围再大也不怕——按位处理, 范围从「键的最大值」变成了「键的位数」,这是它对前两者的真正解放25。 限制在习题 6.12/6.14 说破:负数会崩、小数被截断、字符串要每符号一桶。

3.6 故意低效的五种:认清「差」长什么样

章末一节反例博物馆,每种都有一个性能「亮点」26:

算法复杂度笑点/要点
Stooge 排序O(n^2.71)递归排前 2/3、后 2/3、再前 2/3;比冒泡还差
Slow 排序超多项式「multiply and surrender」(乘而降),作者的恶意之作
排列排序O(n!)不停生成下一个全排列直到有序
Bogosort期望 n!乱序再查,52 张牌成功率约 1/52!;概率为 1 终会排好,但时间无界
睡眠排序依赖最大值键为 K 就等 K 秒再输出;JS 专供,数据一大就崩

这节的教学价值在于:把「复杂度失控」的几种典型形状(指数、阶乘、概率性) 一次性展示,读者日后看到似曾相识的结构能立刻警觉。

4. 作者的判断与证据

  • **「多数情况用 JS 自带 sort」**是实用主义判断,紧跟一句「本章仍要讲清原理」 ——两者不矛盾:选型靠库,理解靠实现16。
  • 比较下界的论证是严格的(信息论 + 斯特林),书中明确标注「不推导」, 只给直觉版二十个问题17。
  • 快排增强集的取舍是经验共识:随机/三值取中/小区间切换/ninther, 与工业实现(Java 双 pivot、V8 TimSort)逐一对应——本章代码与真实引擎 之间的距离被明说23。
  • 不比较排序的限制逐条明写(重复、范围、负数、小数),没有掩盖适用面窄的事实24。

判断(我们的,不是书里的): 本章真正的主线不是「学会十种排序」, 而是选型思维的两连问:第一问「键允许不比较吗」(范围小→位图/计数, 定长可分解→基数),第二问「n 多大、输入有多乱」(小→插入;乱→快排; 要稳定或最坏保证→归并/TimSort;最坏情况就是平均情况的近有序输入→插入/希尔)。 十种算法是这两问的决策树,不是清单。 如果错,会错在: 决策树缺了「外部排序」和「并行排序」两个真实分支—— 书里把外部排序推给系统工具是诚实的,但对「数据装不下内存」这一常见现实, 读者只得到了「别自己写」而没有「那该怎么办」。

5. 边界与局限

  • 堆排序缺席(除了注释提它属第 14 章)——「全部排序算法」的图景要到第 14 章才完整。
  • 外部排序一笔带过,并行/分布式排序没有。
  • TimSort 只讲思想不给实现(近千行的实现,书里明说跳过了)。
  • 稳定性的强转法(扩键)有 O(n) 空间代价,书里未点破。
  • 习题 6.13 那个 Array(10).fill([]) 的坑(十个桶是同一个数组)是 JS 专属, 值得所有读者亲手试一次27。

6. 可带走的

  1. 排序定义两条:非降序 + 输出是输入的排列(空数组不是排序)。
  2. 六维度:内外、原地、在线、稳定、自适应;.sort() 不传函数按字符串排,数字必须 (a,b)=>a-b。
  3. 比较排序下界 O(n log n)(二十个问题);不比才有 O(n)。
  4. O(n²) 四兄弟:冒泡/鸡尾酒/选择/插入;插入是小数组与近有序输入的默认赢家。
  5. 梳排序与希尔的「间距跳跃」思想;Knuth 序列 1,4,13,40…;希尔约 O(n^1.5) 且不稳定。
  6. 快排三个增强:随机或三值取中 pivot、小区间切插入、双 pivot/三路划分(重复键免排)。
  7. 归并:稳定 + 最坏 O(n log n),代价 O(n) 空间;TimSort = 归并+插入+利用有序段,是 V8 的真身。
  8. 不比较三兄弟的限制清单:位图(无重复)计数(范围小)基数(逐位、要稳定、负数/小数会崩)。
  9. 反例博物馆:复杂度失控的四种形状(高次多项式/超多项式/阶乘/概率无界)。
  10. 测试排序的土办法:与内置排序对拍,JSON.stringify 比字符串(习题 6.3)。

7. 原文地图

主题原书章原文位置
排序定义与错例The Sorting Problemtext/17-fm-the-sorting-problem.txt:4(搜「permutation」)
内外/原地/在线/稳定性The Sorting Problemtext/17-fm-the-sorting-problem.txt:19(搜「External」) · text/17-fm-the-sorting-problem.txt:42(搜「In-Place」) · text/17-fm-the-sorting-problem.txt:55(搜「online」) · text/17-fm-the-sorting-problem.txt:71(搜「stable」)
强转稳定(扩键)The Sorting Problemtext/17-fm-the-sorting-problem.txt:88(搜「extended key」)
JS sort 与比较器The Sorting Problemtext/17-fm-the-sorting-problem.txt:109(搜「toSorted」) · text/17-fm-the-sorting-problem.txt:114(搜「12 22 4」)
比较下界(二十个问题)The Sorting Problemtext/17-fm-the-sorting-problem.txt:180(搜「20 questions」)
冒泡与交换检查Sorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:23(搜「bubble up」) · text/18-fm-sorting-with-comparisons.txt:54(搜「n(n」)
鸡尾酒/选择/插入Sorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:64(搜「shuttle」) · text/18-fm-sorting-with-comparisons.txt:140(搜「selectionSort」) · text/18-fm-sorting-with-comparisons.txt:183(搜「insertionSort」)
梳排序(兔子乌龟)Sorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:234(搜「rabbits」) · text/18-fm-sorting-with-comparisons.txt:244(搜「SHRINK_FACTOR」)
希尔(Knuth 序列)Sorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:286(搜「shellSort」)
快排/三值取中/混合/双轴Sorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:339(搜「quickSort」) · text/18-fm-sorting-with-comparisons.txt:391(搜「middle」) · text/18-fm-sorting-with-comparisons.txt:417(搜「CUTOFF」) · text/18-fm-sorting-with-comparisons.txt:456(搜「dualPivot」)
归并与 TimSortSorting with Comparisonstext/18-fm-sorting-with-comparisons.txt:552(搜「mergesort」) · text/18-fm-sorting-with-comparisons.txt:580(搜「Tim sort」)
位图/计数/基数Sorting Without Comparisonstext/19-fm-sorting-without-comparisons.txt:15(搜「suppositions」) · text/19-fm-sorting-without-comparisons.txt:83(搜「countingSort」) · text/19-fm-sorting-without-comparisons.txt:113(搜「Hollerith」)
低效五种Inefficient Sorting Algorithmstext/20-fm-inefficient-sorting-algorithms.txt:12(搜「Stooge」) · text/20-fm-inefficient-sorting-algorithms.txt:42(搜「bogus」) · text/20-fm-inefficient-sorting-algorithms.txt:55(搜「sleepSort」)
习题 6.1–6.14Questionstext/22-fm-questions.txt:4(搜「Forced Reversal」)
答案(三路划分/XOR/fill 坑)Chapter 6text/69-ch06-chapter-6.txt:106(搜「quickSort」) · text/69-ch06-chapter-6.txt:36(搜「XOR」) · text/69-ch06-chapter-6.txt:159(搜「reference to the same array」)

Footnotes

  1. 出处:「Sorting with Comparisons」第 23–54 段(text/18-fm-sorting-with-comparisons.txt:23,搜「bubble up」)。原文:每趟把最大值换到右端;比较总数 (n−1)+(n−2)+…+1 = n(n−1)/2,故 O(n²)。 ↩

  2. 出处:「Chapter 6」第 61–75 段(text/69-ch06-chapter-6.txt:63,搜「swaps」)。答案原文:每趟设 swaps = false,有交换置 true,趟末 if (!swaps) break;——近有序输入提前收工。 ↩

  3. 出处:「Sorting with Comparisons」第 168–214 段(text/18-fm-sorting-with-comparisons.txt:168,搜「playing cards」)。原文:插入排序像理牌,前段已有序、新牌插到位;优化版先把新元素存 temp 再右移,一趟一次写入。 ↩

  4. 出处:「Sorting with Comparisons」第 339–362 段(text/18-fm-sorting-with-comparisons.txt:339,搜「quickSort」)。原文:选最右为 pivot,扫一趟把小的换左侧,pivot 落位 p,递归两段;「平均 O(n log n)」;已排序输入「划分总是只剩一个子数组,相当于选择/冒泡,性能掉到 O(n²)」。 ↩

  5. 出处:「Sorting with Comparisons」第 442–500 段(text/18-fm-sorting-with-comparisons.txt:456,搜「dualPivot」)。原文:双 pivot 把数组分三段;「通常更快——Java 把它用作原生类型数组的默认排序」;书上给了维护五段不变式的完整划分代码。 ↩

  6. 出处:「Sorting Without Comparisons」第 83–103 段(text/19-fm-sorting-without-comparisons.txt:83,搜「countingSort」)。原文:计数表 + 落点表;「最小键(47)的输出从位置 0 起,下一个键因有两个 47 而从位置 2 起」;每个元素落位后对应落点 +1。 ↩ ↩2

  7. 出处:「The Sorting Problem」第 4 段(text/17-fm-the-sorting-problem.txt:4,搜「permutation」)。原文:排序算法「重排列表使键非降序,且输出列表是输入的一个排列,保留所有原记录」。 ↩

  8. 出处:「The Sorting Problem」第 7 段(text/17-fm-the-sorting-problem.txt:7,搜「wrongWayToSort」)。原文给出 const wrongWayToSort = (inputData) => []; 作为「忘记第二条」的反例。 ↩

  9. 出处:「The Sorting Problem」第 19–22 段(text/17-fm-the-sorting-problem.txt:19,搜「External」)。原文:外部排序分段落盘再归并;「对这种大排序任务,你最好使用标准系统 sort 工具,它还可能用并行线程、多 CPU 优化」。 ↩

  10. 出处:「The Sorting Problem」第 42 段(text/17-fm-the-sorting-problem.txt:42,搜「In-Place」)。原文:快排内部用 O(log n) 栈也算原地;归并需要 O(n) 额外空间,属 out-of-place。 ↩

  11. 出处:「The Sorting Problem」第 55–61 段(text/17-fm-the-sorting-problem.txt:55,搜「online」)。原文:在线算法边收边排、保持时刻有序;「在线算法不知道整个输入,必须做出日后可能证明是次优的决定——与贪心算法同样的处境」。 ↩

  12. 出处:「The Sorting Problem」第 71–85 段(text/17-fm-the-sorting-problem.txt:71,搜「stable」)。原文:稳定排序保持相等键的相对顺序;例子:联系人先按名字排、再按星标排,稳定则名字序保住;「正是稳定性让 Joliet 排在 Romeo 前面」。 ↩

  13. 出处:「The Sorting Problem」第 88 段(text/17-fm-the-sorting-problem.txt:88,搜「extended key」)。原文:任何排序都能强转稳定——把键扩成「原键 + 原位置」,按扩展键排序,相等键自动保持原相对顺序,排完丢掉附加字段。 ↩

  14. 出处:「The Sorting Problem」第 32 段(text/17-fm-the-sorting-problem.txt:32,搜「adaptive」)。原文:自适应算法利用输入已有序性;希尔是,快排「可算反自适应」(最坏恰在输入有序时)。 ↩

  15. 出处:「The Sorting Problem」第 109–120 段(text/17-fm-the-sorting-problem.txt:109,搜「toSorted」)。原文:不传比较函数时转字符串按字典序排,[22, 9, 60, 12, 4, 56].sort() 得 [12, 22, 4, 56, 60, 9];传 (a, b) => a - b 得正确数字序。 ↩

  16. 出处:「The Sorting Problem」第 106 段(text/17-fm-the-sorting-problem.txt:106,搜「most effective」)。原文:「尽管本章后面会考虑更多(可能更好)的排序算法,在许多情况下用 JavaScript 自己的 sort 可能最有效。」 ↩ ↩2

  17. 出处:「The Sorting Problem」第 180–186 段(text/17-fm-the-sorting-problem.txt:180,搜「20 questions」)。原文:20 个是非题能从 2²⁰=1,048,576 个可能中锁定;排序要区分 n! 种排列,需 log(n!) 次比较;由斯特林近似 log(n!)=O(n log n),故「任何基于比较的算法至少 O(n log n)」;「若不实际比较,一切赌注作废」。 ↩ ↩2

  18. 出处:「Sorting with Comparisons」第 234–262 段(text/18-fm-sorting-with-comparisons.txt:234,搜「rabbits」)。原文:大值是兔子(快速右移),小值是乌龟(一趟一格);间距每趟除以 1.3,收到 1 退回冒泡;最坏 O(n²),最好 O(n log n)。 ↩

  19. 出处:「Sorting with Comparisons」第 286–305 段(text/18-fm-sorting-with-comparisons.txt:286,搜「shellSort」)。原文:Knuth(1973)序列 1,4,13,40,…(每项 3 倍+1),降序应用;末趟是插入排序但面对近乎有序输入;「得 O(n^1.5) 算法」。 ↩

  20. 出处:「Sorting with Comparisons」第 378–401 段(text/18-fm-sorting-with-comparisons.txt:378,搜「iPivot」)。原文:随机取 pivot「几乎解决了近有序数组的最坏行为,但仍有极低概率一直取到最值」;三值取中:左中右排序后中位数落最右;更强有 ninther。 ↩

  21. 出处:「Sorting with Comparisons」第 414–432 段(text/18-fm-sorting-with-comparisons.txt:417,搜「CUTOFF」)。原文:分段小于 CUTOFF=7 换插入排序;「粗体那几行就是全部改动」。 ↩

  22. 出处:「Chapter 6」第 106–141 段(text/69-ch06-chapter-6.txt:117,搜「[arr[p]」)。答案原文:pivot 归位后,从 p 向左把等于 pivot 的元素换到左端(pl),从 p 向右换到右端(pr);[pl, pr] 全是 pivot,递归只排两侧。 ↩

  23. 出处:「Sorting with Comparisons」第 580 段(text/18-fm-sorting-with-comparisons.txt:580,搜「Tim sort」)。原文:TimSort 稳定自适应,利用已有有序段(run),「Java 用它,JavaScript 的 V8 引擎也用它」;实现近 1000 行,本书不展开,「你已经学齐了构成 TimSort 的所有零件」。 ↩ ↩2

  24. 出处:「Sorting Without Comparisons」第 15–59 段(text/19-fm-sorting-without-comparisons.txt:15,搜「suppositions」)。原文:三条前提——只排数字、范围小、无重复;重复时直接抛错;「不能允许重复键是个严重限制」。 ↩ ↩2

  25. 出处:「Sorting Without Comparisons」第 121–133 段(text/19-fm-sorting-without-comparisons.txt:113,搜「Hollerith」)。原文:分类机按列分桶,从第 6 列收到第 1 列;「收回卡片时发现已按两列有序(回到稳定性一节理解为什么)」;详细实现留到第 10 章用列表模拟桶。 ↩

  26. 出处:「Inefficient Sorting Algorithms」第 12、22、32、42、52–56 段(text/20-fm-inefficient-sorting-algorithms.txt:12,搜「Stooge」;text/20-fm-inefficient-sorting-algorithms.txt:42,搜「bogus」)。原文依次:Stooge O(n^2.71);Slow 排序「multiply and surrender」,C(n)=2C(n/2)+C(n−1)+1;排列排序平均试 n!/2 个;Bogosort 52 张牌约 1/52!;睡眠排序「数据足够大时会崩(太多挂起的 timeout)或失败」。 ↩

  27. 出处:「Chapter 6」第 159 段(text/69-ch06-chapter-6.txt:159,搜「reference to the same array」)。答案原文:Array(10).fill([]) 会让所有桶指向同一个数组;Array(10).map(...) 则因 .map 跳过空位什么都不做。 ↩

第 5 章 设计算法 — 递归、动态规划、蛮力与贪心

Previous Page

第 7 章 选择 — 只找第 k 小,不必全排序

Next Page

On this page

第 6 章 排序 — 从 O(n²) 到 O(n),比较与不比的两条路线1. 顶层全景2. 主线例子:[22, 9, 60, 12, 4, 56] 走四个代表性算法3. 核心原理3.1 先立规矩:排序问题的六个分类维度3.2 比较排序的下界:O(n log n) 是撞不破的墙3.3 O(n²) 一族:简单、稳定(部分)、好懂3.4 快排的三个增强:工程化的完整样本3.5 不比较三兄弟:用键的值换 O(n)3.6 故意低效的五种:认清「差」长什么样4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes