经典排序算法详解：从原理到工程实践的完整指南

经典排序算法详解：从原理到工程实践的完整指南

本文从排序算法的分类与核心概念讲起，逐个拆解8种经典排序算法的执行过程、复杂度推导与稳定性证明，最后落到工程实践（TimSort、IntroSort）和面试高频题型。每个算法配有 Mermaid 流程图解，力求讲清"为什么"而非罗列结论。

目录

• 第1章 排序算法全景：分类、稳定性与复杂度下界
• 第2章 冒泡排序：从朴素到优化的完整推导
• 第3章 选择排序：为什么它总是O(n²)
• 第4章 插入排序：小数组的王者
• 第5章 归并排序：分治的优雅
• 第6章 快速排序：为什么它是实际最快的
• 第7章 堆排序：优先队列的排序
• 第8章 非比较排序：计数、基数与桶排序
• 第9章 工程实践：TimSort、IntroSort与库实现选型
• 第10章 面试高频题型与实战总结

第1章 排序算法全景：分类、稳定性与复杂度下界

1.1 为什么要深入学习排序

排序是计算机科学中最基本的操作之一。你可能会觉得：“调一下 Arrays.sort() 不就行了？” 但理解排序算法的底层原理，在以下场景中不可或缺：

• 面试：快排的 partition 过程、归并的 merge 实现、堆的调整逻辑，是各大厂笔试的高频题
• 工程选型：处理10亿条数据时该用外部归并还是桶排序？小数组为什么用插入排序更快？
• 理解库实现：Java 的 Arrays.sort() 对对象数组用 TimSort、对基本类型用 Dual-Pivot QuickSort，为什么设计不同？

本文不只是列出代码和复杂度表，而是讲清楚每个算法的核心思想、执行过程、为什么有这样的复杂度、为什么稳定或不稳定，以及在工程中如何选择。

1.2 排序算法的分类

排序算法可以从多个维度分类：

#mermaid-svg-WK8FPCmyKawfG2oc{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-WK8FPCmyKawfG2oc .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-WK8FPCmyKawfG2oc .error-icon{fill:#552222;}#mermaid-svg-WK8FPCmyKawfG2oc .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WK8FPCmyKawfG2oc .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WK8FPCmyKawfG2oc .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WK8FPCmyKawfG2oc .marker.cross{stroke:#333333;}#mermaid-svg-WK8FPCmyKawfG2oc svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WK8FPCmyKawfG2oc p{margin:0;}#mermaid-svg-WK8FPCmyKawfG2oc .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-WK8FPCmyKawfG2oc .cluster-label text{fill:#333;}#mermaid-svg-WK8FPCmyKawfG2oc .cluster-label span{color:#333;}#mermaid-svg-WK8FPCmyKawfG2oc .cluster-label span p{background-color:transparent;}#mermaid-svg-WK8FPCmyKawfG2oc .label text,#mermaid-svg-WK8FPCmyKawfG2oc span{fill:#333;color:#333;}#mermaid-svg-WK8FPCmyKawfG2oc .node rect,#mermaid-svg-WK8FPCmyKawfG2oc .node circle,#mermaid-svg-WK8FPCmyKawfG2oc .node ellipse,#mermaid-svg-WK8FPCmyKawfG2oc .node polygon,#mermaid-svg-WK8FPCmyKawfG2oc .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WK8FPCmyKawfG2oc .rough-node .label text,#mermaid-svg-WK8FPCmyKawfG2oc .node .label text,#mermaid-svg-WK8FPCmyKawfG2oc .image-shape .label,#mermaid-svg-WK8FPCmyKawfG2oc .icon-shape .label{text-anchor:middle;}#mermaid-svg-WK8FPCmyKawfG2oc .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-WK8FPCmyKawfG2oc .rough-node .label,#mermaid-svg-WK8FPCmyKawfG2oc .node .label,#mermaid-svg-WK8FPCmyKawfG2oc .image-shape .label,#mermaid-svg-WK8FPCmyKawfG2oc .icon-shape .label{text-align:center;}#mermaid-svg-WK8FPCmyKawfG2oc .node.clickable{cursor:pointer;}#mermaid-svg-WK8FPCmyKawfG2oc .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-WK8FPCmyKawfG2oc .arrowheadPath{fill:#333333;}#mermaid-svg-WK8FPCmyKawfG2oc .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WK8FPCmyKawfG2oc .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WK8FPCmyKawfG2oc .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WK8FPCmyKawfG2oc .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-WK8FPCmyKawfG2oc .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WK8FPCmyKawfG2oc .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-WK8FPCmyKawfG2oc .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WK8FPCmyKawfG2oc .cluster text{fill:#333;}#mermaid-svg-WK8FPCmyKawfG2oc .cluster span{color:#333;}#mermaid-svg-WK8FPCmyKawfG2oc div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WK8FPCmyKawfG2oc .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-WK8FPCmyKawfG2oc rect.text{fill:none;stroke-width:0;}#mermaid-svg-WK8FPCmyKawfG2oc .icon-shape,#mermaid-svg-WK8FPCmyKawfG2oc .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-WK8FPCmyKawfG2oc .icon-shape p,#mermaid-svg-WK8FPCmyKawfG2oc .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-WK8FPCmyKawfG2oc .icon-shape .label rect,#mermaid-svg-WK8FPCmyKawfG2oc .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-WK8FPCmyKawfG2oc .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-WK8FPCmyKawfG2oc .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-WK8FPCmyKawfG2oc :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

排序算法分类全景

比较排序

O(n²) 简单排序

冒泡排序（稳定）

选择排序（不稳定）

插入排序（稳定）

O(n log n) 高效排序

归并排序（稳定）

快速排序（不稳定）

堆排序（不稳定）

非比较排序

计数排序 O(n+k)

基数排序 O(d·n)

桶排序 O(n+k)

图1-1：排序算法分类全景图——比较排序有 O(n log n) 的理论下界，非比较排序可突破下界但要求数据满足特定条件

比较排序 vs 非比较排序是最大的分水岭：

• 比较排序：通过比较两个元素的大小来决定顺序。包括冒泡、选择、插入、归并、快排、堆排。无论怎么优化，最坏情况下至少需要 O(n log n) 次比较（决策树模型可证明）。
• 非比较排序：不通过比较，而是利用元素本身的特性（如取值范围、位数）来排序。包括计数排序、基数排序、桶排序。可以做到 O(n)，但要求数据满足特定约束（如取值范围有限）。

1.3 稳定性：比你想的更重要

稳定性是指：对于相等的元素，排序后它们的相对顺序与排序前一致。

为什么要关心稳定性？考虑一个场景：你有一个学生列表，已经按姓名排序。现在你要按班级排序，如果排序算法是稳定的，那么同一个班级的学生仍然按姓名排序；如果不稳定，同一个班级的学生姓名顺序就乱了。

#mermaid-svg-l1w29QiPln1bdOUh{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-l1w29QiPln1bdOUh .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-l1w29QiPln1bdOUh .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-l1w29QiPln1bdOUh .error-icon{fill:#552222;}#mermaid-svg-l1w29QiPln1bdOUh .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-l1w29QiPln1bdOUh .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-l1w29QiPln1bdOUh .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-l1w29QiPln1bdOUh .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-l1w29QiPln1bdOUh .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-l1w29QiPln1bdOUh .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-l1w29QiPln1bdOUh .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-l1w29QiPln1bdOUh .marker{fill:#333333;stroke:#333333;}#mermaid-svg-l1w29QiPln1bdOUh .marker.cross{stroke:#333333;}#mermaid-svg-l1w29QiPln1bdOUh svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-l1w29QiPln1bdOUh p{margin:0;}#mermaid-svg-l1w29QiPln1bdOUh .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-l1w29QiPln1bdOUh .cluster-label text{fill:#333;}#mermaid-svg-l1w29QiPln1bdOUh .cluster-label span{color:#333;}#mermaid-svg-l1w29QiPln1bdOUh .cluster-label span p{background-color:transparent;}#mermaid-svg-l1w29QiPln1bdOUh .label text,#mermaid-svg-l1w29QiPln1bdOUh span{fill:#333;color:#333;}#mermaid-svg-l1w29QiPln1bdOUh .node rect,#mermaid-svg-l1w29QiPln1bdOUh .node circle,#mermaid-svg-l1w29QiPln1bdOUh .node ellipse,#mermaid-svg-l1w29QiPln1bdOUh .node polygon,#mermaid-svg-l1w29QiPln1bdOUh .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-l1w29QiPln1bdOUh .rough-node .label text,#mermaid-svg-l1w29QiPln1bdOUh .node .label text,#mermaid-svg-l1w29QiPln1bdOUh .image-shape .label,#mermaid-svg-l1w29QiPln1bdOUh .icon-shape .label{text-anchor:middle;}#mermaid-svg-l1w29QiPln1bdOUh .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-l1w29QiPln1bdOUh .rough-node .label,#mermaid-svg-l1w29QiPln1bdOUh .node .label,#mermaid-svg-l1w29QiPln1bdOUh .image-shape .label,#mermaid-svg-l1w29QiPln1bdOUh .icon-shape .label{text-align:center;}#mermaid-svg-l1w29QiPln1bdOUh .node.clickable{cursor:pointer;}#mermaid-svg-l1w29QiPln1bdOUh .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-l1w29QiPln1bdOUh .arrowheadPath{fill:#333333;}#mermaid-svg-l1w29QiPln1bdOUh .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-l1w29QiPln1bdOUh .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-l1w29QiPln1bdOUh .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-l1w29QiPln1bdOUh .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-l1w29QiPln1bdOUh .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-l1w29QiPln1bdOUh .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-l1w29QiPln1bdOUh .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-l1w29QiPln1bdOUh .cluster text{fill:#333;}#mermaid-svg-l1w29QiPln1bdOUh .cluster span{color:#333;}#mermaid-svg-l1w29QiPln1bdOUh div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-l1w29QiPln1bdOUh .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-l1w29QiPln1bdOUh rect.text{fill:none;stroke-width:0;}#mermaid-svg-l1w29QiPln1bdOUh .icon-shape,#mermaid-svg-l1w29QiPln1bdOUh .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-l1w29QiPln1bdOUh .icon-shape p,#mermaid-svg-l1w29QiPln1bdOUh .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-l1w29QiPln1bdOUh .icon-shape .label rect,#mermaid-svg-l1w29QiPln1bdOUh .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-l1w29QiPln1bdOUh .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-l1w29QiPln1bdOUh .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-l1w29QiPln1bdOUh :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

不稳定排序后（按班级）

稳定排序后（按班级）

排序前（按姓名排好）

张三 班级2

李四 班级1

王五 班级2

赵六 班级1

李四 班级1

赵六 班级1

张三 班级2

王五 班级2

赵六 班级1

李四 班级1

王五 班级2

张三 班级2

图1-2：稳定排序保持同班级内姓名顺序不变（绿色），不稳定排序可能打乱（红色）

判断稳定性的通用原则：如果算法中相等元素之间发生了"跨越式交换"（即一个相等元素跳过了另一个相等元素），则不稳定。我们会在每个算法的分析中具体说明。

1.4 比较排序的复杂度下界：O(n log n)

为什么比较排序不能比 O(n log n) 更快？这不是经验结论，而是数学定理。

决策树模型证明：n 个元素有 n! 种排列。每次比较相当于在决策树中走一步（左或右），把可能的排列集合一分为二。要区分 n! 种排列，决策树至少需要 n! 个叶子节点。一棵高度为 h 的二叉树最多有 2^h 个叶子，所以：

2

h

≥

n

!
  

⟹
  

h

≥

log

⁡

2

(

n

!

)

2^h \\geq n! \\implies h \\geq \\log_2(n!)

2h≥n!⟹h≥log2​(n!)

由斯特林公式，log₂(n!) = Θ(n log n)，因此比较排序的最坏时间复杂度下界为 O(n log n)。

这意味着：无论你怎么设计比较排序算法，最坏情况下不可能优于 O(n log n)。这是信息论给出的硬限制——每次比较只提供 1 bit 的信息，而排序需要 log₂(n!) bits 的信息量。

非比较排序之所以能突破这个下界，是因为它不依赖比较，而是利用元素的额外信息（如取值范围），每次操作获取超过 1 bit 的信息。

1.5 全文复杂度速查表

表1-1：9种排序算法复杂度速查表——k为取值范围，d为最大位数

接下来逐个深入每个算法。

第2章 冒泡排序：从朴素到优化的完整推导

2.1 核心思想

冒泡排序的思路最直观：相邻元素两两比较，逆序则交换。每一轮遍历都会把当前未排序部分的最大值"冒泡"到末尾，就像水底的气泡浮向水面。

为什么是"相邻"比较？因为只有相邻交换才能保证稳定性——不相邻的交换可能跨过相等的元素。这一点在选择排序中会形成对比。

2.2 执行过程图解

以 [5, 3, 8, 1, 2] 为例，演示完整执行过程：

#mermaid-svg-unbOt12un9hKJ58d{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-unbOt12un9hKJ58d .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-unbOt12un9hKJ58d .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-unbOt12un9hKJ58d .error-icon{fill:#552222;}#mermaid-svg-unbOt12un9hKJ58d .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-unbOt12un9hKJ58d .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-unbOt12un9hKJ58d .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-unbOt12un9hKJ58d .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-unbOt12un9hKJ58d .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-unbOt12un9hKJ58d .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-unbOt12un9hKJ58d .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-unbOt12un9hKJ58d .marker{fill:#333333;stroke:#333333;}#mermaid-svg-unbOt12un9hKJ58d .marker.cross{stroke:#333333;}#mermaid-svg-unbOt12un9hKJ58d svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-unbOt12un9hKJ58d p{margin:0;}#mermaid-svg-unbOt12un9hKJ58d .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-unbOt12un9hKJ58d .cluster-label text{fill:#333;}#mermaid-svg-unbOt12un9hKJ58d .cluster-label span{color:#333;}#mermaid-svg-unbOt12un9hKJ58d .cluster-label span p{background-color:transparent;}#mermaid-svg-unbOt12un9hKJ58d .label text,#mermaid-svg-unbOt12un9hKJ58d span{fill:#333;color:#333;}#mermaid-svg-unbOt12un9hKJ58d .node rect,#mermaid-svg-unbOt12un9hKJ58d .node circle,#mermaid-svg-unbOt12un9hKJ58d .node ellipse,#mermaid-svg-unbOt12un9hKJ58d .node polygon,#mermaid-svg-unbOt12un9hKJ58d .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-unbOt12un9hKJ58d .rough-node .label text,#mermaid-svg-unbOt12un9hKJ58d .node .label text,#mermaid-svg-unbOt12un9hKJ58d .image-shape .label,#mermaid-svg-unbOt12un9hKJ58d .icon-shape .label{text-anchor:middle;}#mermaid-svg-unbOt12un9hKJ58d .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-unbOt12un9hKJ58d .rough-node .label,#mermaid-svg-unbOt12un9hKJ58d .node .label,#mermaid-svg-unbOt12un9hKJ58d .image-shape .label,#mermaid-svg-unbOt12un9hKJ58d .icon-shape .label{text-align:center;}#mermaid-svg-unbOt12un9hKJ58d .node.clickable{cursor:pointer;}#mermaid-svg-unbOt12un9hKJ58d .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-unbOt12un9hKJ58d .arrowheadPath{fill:#333333;}#mermaid-svg-unbOt12un9hKJ58d .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-unbOt12un9hKJ58d .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-unbOt12un9hKJ58d .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-unbOt12un9hKJ58d .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-unbOt12un9hKJ58d .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-unbOt12un9hKJ58d .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-unbOt12un9hKJ58d .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-unbOt12un9hKJ58d .cluster text{fill:#333;}#mermaid-svg-unbOt12un9hKJ58d .cluster span{color:#333;}#mermaid-svg-unbOt12un9hKJ58d div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-unbOt12un9hKJ58d .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-unbOt12un9hKJ58d rect.text{fill:none;stroke-width:0;}#mermaid-svg-unbOt12un9hKJ58d .icon-shape,#mermaid-svg-unbOt12un9hKJ58d .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-unbOt12un9hKJ58d .icon-shape p,#mermaid-svg-unbOt12un9hKJ58d .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-unbOt12un9hKJ58d .icon-shape .label rect,#mermaid-svg-unbOt12un9hKJ58d .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-unbOt12un9hKJ58d .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-unbOt12un9hKJ58d .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-unbOt12un9hKJ58d :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第4轮

[1, 2, 3, 5, 8] 比较1和2 → 不交换 → 有序！

第3轮

[3, 1, 2, 5, 8] 比较3和1 → 交换 → [1, 3, 2, 5, 8]

[1, 3, 2, 5, 8] 比较3和2 → 交换 → [1, 2, 3, 5, 8]

第2轮：在剩余[3,5,1,2]中冒泡

[3, 5, 1, 2, 8] 比较3和5 → 不交换

[3, 5, 1, 2, 8] 比较5和1 → 交换 → [3, 1, 5, 2, 8]

[3, 1, 5, 2, 8] 比较5和2 → 交换 → [3, 1, 2, 5, 8]

第1轮：把最大值8冒泡到末尾

[5, 3, 8, 1, 2] 比较5和3 → 交换 → [3, 5, 8, 1, 2]

[3, 5, 8, 1, 2] 比较5和8 → 不交换

[3, 5, 8, 1, 2] 比较8和1 → 交换 → [3, 5, 1, 8, 2]

[3, 5, 1, 8, 2] 比较8和2 → 交换 → [3, 5, 1, 2, 8]

图2-1：冒泡排序完整执行过程——每轮把一个最大值"冒泡"到末尾（橙色），第4轮无交换说明已有序（绿色）

2.3 代码实现

2.3.1 朴素版本

public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环：共需 n-1 轮
for (int i = 0; i < n – 1; i++) {
// 内层循环：每轮比较到 n-1-i（末尾 i 个已排好）
for (int j = 0; j < n – 1 – i; j++) {
if (arr[j] > arr[j + 1]) {
// 相邻逆序则交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

注意比较条件是 arr[j] > arr[j + 1] 而不是 >=。如果用 >=，相等的元素也会交换，虽然结果不影响顺序，但会多做无意义的交换操作，更重要的是会破坏稳定性——相等元素不应该被交换。

2.3.2 优化版本：提前终止

朴素版本的问题在于：即使数组已经有序，它也会傻傻地跑完所有轮次。优化思路是加一个 swapped 标记——如果某一轮没有任何交换，说明数组已经有序，可以提前终止。

public static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
boolean swapped = false; // 标记本轮是否发生交换
for (int j = 0; j < n – 1 – i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // 本轮无交换，已有序
}
}

这个优化让最好情况（已有序数组）从 O(n²) 降到 O(n)：只需一轮遍历，发现没有交换就退出。

2.3.3 终极优化：记录最后交换位置

还可以进一步优化：记录每轮最后一次交换的位置，该位置之后的元素已经有序，下一轮不需要再比较。

public static void bubbleSortFinal(int[] arr) {
int n = arr.length;
int lastSwapPos = n – 1; // 最后交换位置
while (lastSwapPos > 0) {
int k = lastSwapPos;
lastSwapPos = 0; // 重置，如果本轮无交换则为0，循环结束
for (int j = 0; j < k; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
lastSwapPos = j; // 更新最后交换位置
}
}
}
}

这个版本对"尾部已基本有序"的数组效果最好。例如 [3, 1, 2, 4, 5, 6, 7, 8]，第一轮交换在位置1就结束了，后续只需要比较前3个元素。

2.4 复杂度分析

时间复杂度：

为什么平均是O(n²)：这和逆序对有关。一个长度为n的数组，平均有 n(n-1)/4 个逆序对。冒泡排序每次交换恰好消除一个逆序对，所以平均交换次数是 O(n²)。

空间复杂度：O(1)，原地排序，只需要一个临时变量用于交换。

2.5 稳定性证明

冒泡排序是稳定的。

证明：冒泡排序只比较相邻元素，且比较条件是 >（严格大于）。对于两个相等的元素 a[i] 和 a[j]（i < j），arr[j] > arr[j+1] 条件不成立，不会发生交换，因此它们的相对顺序不会改变。

关键在于"相邻"和"严格大于"两个条件缺一不可。如果不是相邻交换（如选择排序），即使比较条件是 > 也可能不稳定；如果用 >=，相等的相邻元素也会交换，同样不稳定。

2.6 适用场景与局限

适用场景：

• 教学：最直观的排序算法，适合入门
• 数据量极小（n < 20）且对代码简洁性要求高
• 数据近乎有序时，优化版冒泡接近 O(n)

局限：

• 平均 O(n²) 太慢，不适合生产环境
• 交换操作多（每次只消除一个逆序对），常数因子较大

第3章 选择排序：为什么它总是O(n²)

3.1 核心思想

选择排序的思路是：每轮从未排序部分找到最小值，放到已排序部分的末尾。它和冒泡排序的区别在于——冒泡是不断交换把最大值"推"到末尾，选择是先找到最小值再一次性交换到位。

选择排序的优势在于交换次数最少：n 个元素最多交换 n-1 次。这对于"交换代价高"的场景（如外部排序中移动大文件）很有价值。

3.2 执行过程图解

以 [5, 3, 8, 1, 2] 为例：

#mermaid-svg-MxEOALRK8R7wcFqa{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-MxEOALRK8R7wcFqa .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-MxEOALRK8R7wcFqa .error-icon{fill:#552222;}#mermaid-svg-MxEOALRK8R7wcFqa .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-MxEOALRK8R7wcFqa .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-MxEOALRK8R7wcFqa .marker{fill:#333333;stroke:#333333;}#mermaid-svg-MxEOALRK8R7wcFqa .marker.cross{stroke:#333333;}#mermaid-svg-MxEOALRK8R7wcFqa svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-MxEOALRK8R7wcFqa p{margin:0;}#mermaid-svg-MxEOALRK8R7wcFqa .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-MxEOALRK8R7wcFqa .cluster-label text{fill:#333;}#mermaid-svg-MxEOALRK8R7wcFqa .cluster-label span{color:#333;}#mermaid-svg-MxEOALRK8R7wcFqa .cluster-label span p{background-color:transparent;}#mermaid-svg-MxEOALRK8R7wcFqa .label text,#mermaid-svg-MxEOALRK8R7wcFqa span{fill:#333;color:#333;}#mermaid-svg-MxEOALRK8R7wcFqa .node rect,#mermaid-svg-MxEOALRK8R7wcFqa .node circle,#mermaid-svg-MxEOALRK8R7wcFqa .node ellipse,#mermaid-svg-MxEOALRK8R7wcFqa .node polygon,#mermaid-svg-MxEOALRK8R7wcFqa .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-MxEOALRK8R7wcFqa .rough-node .label text,#mermaid-svg-MxEOALRK8R7wcFqa .node .label text,#mermaid-svg-MxEOALRK8R7wcFqa .image-shape .label,#mermaid-svg-MxEOALRK8R7wcFqa .icon-shape .label{text-anchor:middle;}#mermaid-svg-MxEOALRK8R7wcFqa .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-MxEOALRK8R7wcFqa .rough-node .label,#mermaid-svg-MxEOALRK8R7wcFqa .node .label,#mermaid-svg-MxEOALRK8R7wcFqa .image-shape .label,#mermaid-svg-MxEOALRK8R7wcFqa .icon-shape .label{text-align:center;}#mermaid-svg-MxEOALRK8R7wcFqa .node.clickable{cursor:pointer;}#mermaid-svg-MxEOALRK8R7wcFqa .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-MxEOALRK8R7wcFqa .arrowheadPath{fill:#333333;}#mermaid-svg-MxEOALRK8R7wcFqa .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-MxEOALRK8R7wcFqa .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-MxEOALRK8R7wcFqa .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-MxEOALRK8R7wcFqa .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-MxEOALRK8R7wcFqa .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-MxEOALRK8R7wcFqa .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-MxEOALRK8R7wcFqa .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-MxEOALRK8R7wcFqa .cluster text{fill:#333;}#mermaid-svg-MxEOALRK8R7wcFqa .cluster span{color:#333;}#mermaid-svg-MxEOALRK8R7wcFqa div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-MxEOALRK8R7wcFqa .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-MxEOALRK8R7wcFqa rect.text{fill:none;stroke-width:0;}#mermaid-svg-MxEOALRK8R7wcFqa .icon-shape,#mermaid-svg-MxEOALRK8R7wcFqa .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-MxEOALRK8R7wcFqa .icon-shape p,#mermaid-svg-MxEOALRK8R7wcFqa .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-MxEOALRK8R7wcFqa .icon-shape .label rect,#mermaid-svg-MxEOALRK8R7wcFqa .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-MxEOALRK8R7wcFqa .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-MxEOALRK8R7wcFqa .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-MxEOALRK8R7wcFqa :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第4轮：在[5,8]中找最小值

扫描 → 最小值=5（索引3），已在正确位置

交换arr[3]和arr[3] → [1, 2, 3, 5, 8]

第3轮：在[8,5,3]中找最小值

扫描 → 最小值=3（原索引4）

交换arr[2]和arr[4] → [1, 2, 3, 5, 8]

第2轮：在[3,8,5,2]中找最小值

扫描 → 最小值=2（原索引4）

交换arr[1]和arr[4] → [1, 2, 8, 5, 3]

第1轮：在[5,3,8,1,2]中找最小值

扫描全部 → 最小值=1（索引3）

交换arr[0]和arr[3] → [1, 3, 8, 5, 2]

图3-1：选择排序执行过程——每轮找最小值并与当前位置交换（橙色为本轮交换，绿色为已排序部分）

3.3 代码实现

public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n – 1; i++) {
int minIdx = i; // 假设当前位置就是最小值
// 在未排序部分找最小值的索引
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 把最小值交换到当前位置
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}

注意比较条件是 <（严格小于），目的是找到真正最小的元素。如果用 <=，会多做无意义的赋值（虽然不影响结果）。

3.4 复杂度分析

时间复杂度：

选择排序最特殊的一点：它的最好、平均、最坏情况都是 O(n²)。原因在于，无论数据是否有序，每一轮都必须完整扫描未排序部分来确认最小值——它不像冒泡排序那样能通过"无交换"提前退出。

具体计算比较次数：第1轮比较 n-1 次，第2轮 n-2 次，…，最后一轮 1 次，总计 1 + 2 + … + (n-1) = n(n-1)/2，即 O(n²)。

但交换次数确实是 O(n)：每轮最多一次交换，总计最多 n-1 次。这是选择排序比较次数和交换次数的显著不对称。

空间复杂度：O(1)，原地排序。

3.5 稳定性分析

选择排序是不稳定的。

这是初学者常犯的错误——很多人以为选择排序是稳定的，因为看起来它只是"找最小值再交换"。问题出在交换这一步。

反例：考虑数组 [5a, 5b, 3]（5a 和 5b 值相等，用下标区分）。

第1轮：在 [5a, 5b, 3] 中找最小值 → 3（索引2）
交换 arr[0] 和 arr[2] → [3, 5b, 5a]

5a 原来在 5b 前面，交换后 5a 跑到了 5b 后面。相对顺序被破坏了。

问题的根源是：选择排序的交换不是相邻交换，而是跨越式交换——把最小值从远处搬到当前位置时，可能跨过与当前位置元素相等的其他元素。

#mermaid-svg-P8izXxG9ns12lymS{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-P8izXxG9ns12lymS .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-P8izXxG9ns12lymS .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-P8izXxG9ns12lymS .error-icon{fill:#552222;}#mermaid-svg-P8izXxG9ns12lymS .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-P8izXxG9ns12lymS .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-P8izXxG9ns12lymS .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-P8izXxG9ns12lymS .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-P8izXxG9ns12lymS .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-P8izXxG9ns12lymS .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-P8izXxG9ns12lymS .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-P8izXxG9ns12lymS .marker{fill:#333333;stroke:#333333;}#mermaid-svg-P8izXxG9ns12lymS .marker.cross{stroke:#333333;}#mermaid-svg-P8izXxG9ns12lymS svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-P8izXxG9ns12lymS p{margin:0;}#mermaid-svg-P8izXxG9ns12lymS .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-P8izXxG9ns12lymS .cluster-label text{fill:#333;}#mermaid-svg-P8izXxG9ns12lymS .cluster-label span{color:#333;}#mermaid-svg-P8izXxG9ns12lymS .cluster-label span p{background-color:transparent;}#mermaid-svg-P8izXxG9ns12lymS .label text,#mermaid-svg-P8izXxG9ns12lymS span{fill:#333;color:#333;}#mermaid-svg-P8izXxG9ns12lymS .node rect,#mermaid-svg-P8izXxG9ns12lymS .node circle,#mermaid-svg-P8izXxG9ns12lymS .node ellipse,#mermaid-svg-P8izXxG9ns12lymS .node polygon,#mermaid-svg-P8izXxG9ns12lymS .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-P8izXxG9ns12lymS .rough-node .label text,#mermaid-svg-P8izXxG9ns12lymS .node .label text,#mermaid-svg-P8izXxG9ns12lymS .image-shape .label,#mermaid-svg-P8izXxG9ns12lymS .icon-shape .label{text-anchor:middle;}#mermaid-svg-P8izXxG9ns12lymS .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-P8izXxG9ns12lymS .rough-node .label,#mermaid-svg-P8izXxG9ns12lymS .node .label,#mermaid-svg-P8izXxG9ns12lymS .image-shape .label,#mermaid-svg-P8izXxG9ns12lymS .icon-shape .label{text-align:center;}#mermaid-svg-P8izXxG9ns12lymS .node.clickable{cursor:pointer;}#mermaid-svg-P8izXxG9ns12lymS .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-P8izXxG9ns12lymS .arrowheadPath{fill:#333333;}#mermaid-svg-P8izXxG9ns12lymS .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-P8izXxG9ns12lymS .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-P8izXxG9ns12lymS .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-P8izXxG9ns12lymS .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-P8izXxG9ns12lymS .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-P8izXxG9ns12lymS .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-P8izXxG9ns12lymS .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-P8izXxG9ns12lymS .cluster text{fill:#333;}#mermaid-svg-P8izXxG9ns12lymS .cluster span{color:#333;}#mermaid-svg-P8izXxG9ns12lymS div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-P8izXxG9ns12lymS .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-P8izXxG9ns12lymS rect.text{fill:none;stroke-width:0;}#mermaid-svg-P8izXxG9ns12lymS .icon-shape,#mermaid-svg-P8izXxG9ns12lymS .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-P8izXxG9ns12lymS .icon-shape p,#mermaid-svg-P8izXxG9ns12lymS .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-P8izXxG9ns12lymS .icon-shape .label rect,#mermaid-svg-P8izXxG9ns12lymS .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-P8izXxG9ns12lymS .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-P8izXxG9ns12lymS .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-P8izXxG9ns12lymS :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

选择排序不稳定示例

找最小值=3

[5a, 5b, 3]

交换 arr[0]↔arr[2]

[3, 5b, 5a]

5a 原在5b前

交换后5a在5b后 ← 不稳定！

图3-2：选择排序不稳定的原因——跨越式交换把5a跳过了5b

3.6 选择排序 vs 冒泡排序

选择排序的唯一优势是交换次数最少。这在元素本身很大（如大对象、文件）且比较操作很快时才有意义——此时减少交换比减少比较更重要。

第4章 插入排序：小数组的王者

4.1 核心思想

插入排序模拟整理扑克牌的过程：左手拿着已排好序的牌，右手从桌上拿起一张新牌，从右向左在左手牌中找到合适位置插入。

与冒泡和选择的"每轮选极值"不同，插入排序是"每轮处理一个元素，插入到正确位置"。这个思路的关键优势是：对于近乎有序的数据，插入排序接近 O(n)，因为每个元素只需要比较一两次就能找到位置。

4.2 执行过程图解

以 [5, 3, 8, 1, 2] 为例：

#mermaid-svg-lWBmtuhqFPVz6uSR{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-lWBmtuhqFPVz6uSR .error-icon{fill:#552222;}#mermaid-svg-lWBmtuhqFPVz6uSR .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-lWBmtuhqFPVz6uSR .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-lWBmtuhqFPVz6uSR .marker{fill:#333333;stroke:#333333;}#mermaid-svg-lWBmtuhqFPVz6uSR .marker.cross{stroke:#333333;}#mermaid-svg-lWBmtuhqFPVz6uSR svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-lWBmtuhqFPVz6uSR p{margin:0;}#mermaid-svg-lWBmtuhqFPVz6uSR .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster-label text{fill:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster-label span{color:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster-label span p{background-color:transparent;}#mermaid-svg-lWBmtuhqFPVz6uSR .label text,#mermaid-svg-lWBmtuhqFPVz6uSR span{fill:#333;color:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR .node rect,#mermaid-svg-lWBmtuhqFPVz6uSR .node circle,#mermaid-svg-lWBmtuhqFPVz6uSR .node ellipse,#mermaid-svg-lWBmtuhqFPVz6uSR .node polygon,#mermaid-svg-lWBmtuhqFPVz6uSR .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-lWBmtuhqFPVz6uSR .rough-node .label text,#mermaid-svg-lWBmtuhqFPVz6uSR .node .label text,#mermaid-svg-lWBmtuhqFPVz6uSR .image-shape .label,#mermaid-svg-lWBmtuhqFPVz6uSR .icon-shape .label{text-anchor:middle;}#mermaid-svg-lWBmtuhqFPVz6uSR .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-lWBmtuhqFPVz6uSR .rough-node .label,#mermaid-svg-lWBmtuhqFPVz6uSR .node .label,#mermaid-svg-lWBmtuhqFPVz6uSR .image-shape .label,#mermaid-svg-lWBmtuhqFPVz6uSR .icon-shape .label{text-align:center;}#mermaid-svg-lWBmtuhqFPVz6uSR .node.clickable{cursor:pointer;}#mermaid-svg-lWBmtuhqFPVz6uSR .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-lWBmtuhqFPVz6uSR .arrowheadPath{fill:#333333;}#mermaid-svg-lWBmtuhqFPVz6uSR .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-lWBmtuhqFPVz6uSR .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-lWBmtuhqFPVz6uSR .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-lWBmtuhqFPVz6uSR .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-lWBmtuhqFPVz6uSR .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-lWBmtuhqFPVz6uSR .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster text{fill:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR .cluster span{color:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-lWBmtuhqFPVz6uSR .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-lWBmtuhqFPVz6uSR rect.text{fill:none;stroke-width:0;}#mermaid-svg-lWBmtuhqFPVz6uSR .icon-shape,#mermaid-svg-lWBmtuhqFPVz6uSR .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-lWBmtuhqFPVz6uSR .icon-shape p,#mermaid-svg-lWBmtuhqFPVz6uSR .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-lWBmtuhqFPVz6uSR .icon-shape .label rect,#mermaid-svg-lWBmtuhqFPVz6uSR .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-lWBmtuhqFPVz6uSR .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-lWBmtuhqFPVz6uSR .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-lWBmtuhqFPVz6uSR :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

第4步：取出2，插入到[1,3,5,8]中

2 < 8，8右移

2 < 5，5右移

2 < 3，3右移

2 > 1，插入到位置1 → [|1, 2, 3, 5, 8|]

第3步：取出1，插入到[3,5,8]中

1 < 8，8右移 → [3, 5, _, 8, 2]

1 < 5，5右移 → [3, _, 5, 8, 2]

1 < 3，3右移 → [_, 3, 5, 8, 2]

1放到位置0 → [|1, 3, 5, 8|, 2]

第2步：取出8，插入到[3,5]中

8 > 5，直接放末尾 → [|3, 5, 8|, 1, 2]

第1步：取出3，插入到[5]中

3 < 5，5右移 → [_, 5, 8, 1, 2]

3放到位置0 → [|3, 5|, 8, 1, 2]

初始：已排序=[5]，待排序=[3,8,1,2]

[|5|, 3, 8, 1, 2]

图4-1：插入排序执行过程——绿色竖线左侧为已排序部分，每步取出一个元素从右向左比较并插入

4.3 代码实现

public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 取出待插入元素
int j = i – 1;
// 从右向左找插入位置，大于key的元素右移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 元素右移
j—;
}
arr[j + 1] = key; // 插入到正确位置
}
}

注意 while 条件中的 arr[j] > key 用的是严格大于。如果改成 >=，相等的元素也会被右移，导致相等元素的相对顺序被破坏——这就变成不稳定的了。所以这里用 > 既保证了稳定性，又避免了不必要的移动。

4.4 复杂度分析

时间复杂度：

插入排序的时间复杂度与逆序对数量直接相关。每次内层循环的右移操作恰好消除一个逆序对。逆序对数量为 m 时，时间复杂度为 O(n + m)：

• 有序数组：m = 0，总比较 n-1 次，O(n)
• 逆序数组：m = n(n-1)/2，O(n²)
• 随机数组：m ≈ n(n-1)/4，O(n²)

这就是为什么插入排序对"近乎有序"的数据特别快——逆序对少，比较和移动次数就少。

空间复杂度：O(1)，原地排序。

4.5 稳定性证明

插入排序是稳定的。

证明：插入排序从右向左比较，遇到 arr[j] > key 才右移。对于相等的元素 arr[j] 和 key（即 arr[j] == key），条件 arr[j] > key 不成立，不会右移，key 被插入到 arr[j] 的后面。由于 key 原本就在 arr[j] 后面（i > j），所以相对顺序不变。

4.6 为什么小数组用插入排序

这是工程中最重要的一点。Java 的 Arrays.sort() 对元素数小于47的数组使用插入排序，C++ STL 的 sort() 在递归到小区间时也切换为插入排序。为什么？

原因1：常数因子小。 插入排序的内部循环非常简单——一次比较、一次赋值、一次自减。没有函数调用开销，没有递归开销。对于小数组，O(n²) 的常数因子比 O(n log n) 算法的常数因子小得多。

原因2：缓存友好。 插入排序只访问相邻位置的数据，充分利用 CPU 缓存的局部性。快排和归并排序的跳跃式访问模式导致更多缓存未命中。

原因3：自适应。 如果小数组恰好部分有序（这在快排递归分区后很常见），插入排序会更快。

#mermaid-svg-pvRKI6EYTeCuI32d{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-pvRKI6EYTeCuI32d .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-pvRKI6EYTeCuI32d .error-icon{fill:#552222;}#mermaid-svg-pvRKI6EYTeCuI32d .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-pvRKI6EYTeCuI32d .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-pvRKI6EYTeCuI32d .marker{fill:#333333;stroke:#333333;}#mermaid-svg-pvRKI6EYTeCuI32d .marker.cross{stroke:#333333;}#mermaid-svg-pvRKI6EYTeCuI32d svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-pvRKI6EYTeCuI32d p{margin:0;}#mermaid-svg-pvRKI6EYTeCuI32d .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-pvRKI6EYTeCuI32d .cluster-label text{fill:#333;}#mermaid-svg-pvRKI6EYTeCuI32d .cluster-label span{color:#333;}#mermaid-svg-pvRKI6EYTeCuI32d .cluster-label span p{background-color:transparent;}#mermaid-svg-pvRKI6EYTeCuI32d .label text,#mermaid-svg-pvRKI6EYTeCuI32d span{fill:#333;color:#333;}#mermaid-svg-pvRKI6EYTeCuI32d .node rect,#mermaid-svg-pvRKI6EYTeCuI32d .node circle,#mermaid-svg-pvRKI6EYTeCuI32d .node ellipse,#mermaid-svg-pvRKI6EYTeCuI32d .node polygon,#mermaid-svg-pvRKI6EYTeCuI32d .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-pvRKI6EYTeCuI32d .rough-node .label text,#mermaid-svg-pvRKI6EYTeCuI32d .node .label text,#mermaid-svg-pvRKI6EYTeCuI32d .image-shape .label,#mermaid-svg-pvRKI6EYTeCuI32d .icon-shape .label{text-anchor:middle;}#mermaid-svg-pvRKI6EYTeCuI32d .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-pvRKI6EYTeCuI32d .rough-node .label,#mermaid-svg-pvRKI6EYTeCuI32d .node .label,#mermaid-svg-pvRKI6EYTeCuI32d .image-shape .label,#mermaid-svg-pvRKI6EYTeCuI32d .icon-shape .label{text-align:center;}#mermaid-svg-pvRKI6EYTeCuI32d .node.clickable{cursor:pointer;}#mermaid-svg-pvRKI6EYTeCuI32d .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-pvRKI6EYTeCuI32d .arrowheadPath{fill:#333333;}#mermaid-svg-pvRKI6EYTeCuI32d .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-pvRKI6EYTeCuI32d .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-pvRKI6EYTeCuI32d .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-pvRKI6EYTeCuI32d .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-pvRKI6EYTeCuI32d .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-pvRKI6EYTeCuI32d .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-pvRKI6EYTeCuI32d .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-pvRKI6EYTeCuI32d .cluster text{fill:#333;}#mermaid-svg-pvRKI6EYTeCuI32d .cluster span{color:#333;}#mermaid-svg-pvRKI6EYTeCuI32d div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-pvRKI6EYTeCuI32d .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-pvRKI6EYTeCuI32d rect.text{fill:none;stroke-width:0;}#mermaid-svg-pvRKI6EYTeCuI32d .icon-shape,#mermaid-svg-pvRKI6EYTeCuI32d .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-pvRKI6EYTeCuI32d .icon-shape p,#mermaid-svg-pvRKI6EYTeCuI32d .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-pvRKI6EYTeCuI32d .icon-shape .label rect,#mermaid-svg-pvRKI6EYTeCuI32d .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-pvRKI6EYTeCuI32d .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-pvRKI6EYTeCuI32d .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-pvRKI6EYTeCuI32d :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

混合排序策略（Java Arrays.sort原理）

是

是

否

否

输入数组 n

n ≥ 47?

Dual-Pivot快排

子数组 < 47?

切换为插入排序

排序完成

图4-2：Java Arrays.sort 的混合策略——大数组用快排分区，小区间切换为插入排序

4.7 二分插入排序

插入排序的一个变体：用二分查找来找插入位置，减少比较次数。但元素移动次数不变（还是要右移腾出空间），所以时间复杂度仍然是 O(n²)，只是比较次数从 O(n²) 降到 O(n log n)。

public static void binaryInsertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
// 二分查找插入位置
int lo = 0, hi = i;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (arr[mid] <= key) { // 注意用 <=，找第一个>key的位置
lo = mid + 1;
} else {
hi = mid;
}
}
// 将 [lo, i-1] 的元素右移
System.arraycopy(arr, lo, arr, lo + 1, i – lo);
arr[lo] = key;
}
}

二分插入排序在以下场景有优势：比较操作很昂贵（如字符串比较）。因为二分查找把比较次数从 O(n) 降到了 O(log n)。但对于整数排序，比较很快，移动才是瓶颈，二分插入排序的提升不明显。

注意二分查找中用的是 arr[mid] <= key（带等号），这保证了相等元素的稳定性——找到的是第一个大于 key 的位置，key 被插入到相等元素的后面。

4.8 希尔排序：插入排序的进阶

希尔排序（Shell Sort）是插入排序的改进版，由 Donald Shell 于1959年提出。核心思想是先做远距离交换消除大量逆序对，再逐渐缩小间隔做精细排序。

#mermaid-svg-RtBUZtfgt4hNmaiU{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-RtBUZtfgt4hNmaiU .error-icon{fill:#552222;}#mermaid-svg-RtBUZtfgt4hNmaiU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RtBUZtfgt4hNmaiU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RtBUZtfgt4hNmaiU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-RtBUZtfgt4hNmaiU .marker.cross{stroke:#333333;}#mermaid-svg-RtBUZtfgt4hNmaiU svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RtBUZtfgt4hNmaiU p{margin:0;}#mermaid-svg-RtBUZtfgt4hNmaiU .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster-label text{fill:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster-label span{color:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster-label span p{background-color:transparent;}#mermaid-svg-RtBUZtfgt4hNmaiU .label text,#mermaid-svg-RtBUZtfgt4hNmaiU span{fill:#333;color:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU .node rect,#mermaid-svg-RtBUZtfgt4hNmaiU .node circle,#mermaid-svg-RtBUZtfgt4hNmaiU .node ellipse,#mermaid-svg-RtBUZtfgt4hNmaiU .node polygon,#mermaid-svg-RtBUZtfgt4hNmaiU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RtBUZtfgt4hNmaiU .rough-node .label text,#mermaid-svg-RtBUZtfgt4hNmaiU .node .label text,#mermaid-svg-RtBUZtfgt4hNmaiU .image-shape .label,#mermaid-svg-RtBUZtfgt4hNmaiU .icon-shape .label{text-anchor:middle;}#mermaid-svg-RtBUZtfgt4hNmaiU .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-RtBUZtfgt4hNmaiU .rough-node .label,#mermaid-svg-RtBUZtfgt4hNmaiU .node .label,#mermaid-svg-RtBUZtfgt4hNmaiU .image-shape .label,#mermaid-svg-RtBUZtfgt4hNmaiU .icon-shape .label{text-align:center;}#mermaid-svg-RtBUZtfgt4hNmaiU .node.clickable{cursor:pointer;}#mermaid-svg-RtBUZtfgt4hNmaiU .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-RtBUZtfgt4hNmaiU .arrowheadPath{fill:#333333;}#mermaid-svg-RtBUZtfgt4hNmaiU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RtBUZtfgt4hNmaiU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RtBUZtfgt4hNmaiU .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-RtBUZtfgt4hNmaiU .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-RtBUZtfgt4hNmaiU .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-RtBUZtfgt4hNmaiU .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster text{fill:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU .cluster span{color:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RtBUZtfgt4hNmaiU .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-RtBUZtfgt4hNmaiU rect.text{fill:none;stroke-width:0;}#mermaid-svg-RtBUZtfgt4hNmaiU .icon-shape,#mermaid-svg-RtBUZtfgt4hNmaiU .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-RtBUZtfgt4hNmaiU .icon-shape p,#mermaid-svg-RtBUZtfgt4hNmaiU .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-RtBUZtfgt4hNmaiU .icon-shape .label rect,#mermaid-svg-RtBUZtfgt4hNmaiU .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-RtBUZtfgt4hNmaiU .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-RtBUZtfgt4hNmaiU .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-RtBUZtfgt4hNmaiU :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

希尔排序 gap=3 → gap=1

gap=3: [5,3,8,1,2,7,4,6]

分组: [5,1,4] [3,2,6] [8,7]

各组插入排序: [1,2,7,4,3,6,5,8]

gap=1: 标准插入排序

[1,2,3,4,5,6,7,8]

图4-3：希尔排序——先以gap=3分组排序消除远距离逆序对，再以gap=1做精细插入排序

希尔排序的关键在于**间隔序列（gap sequence）**的选择：

希尔排序的时间复杂度依赖于间隔序列，至今没有精确的平均复杂度分析。它是不稳定的（远距离交换可能跨过相等元素），但在中等规模数据（n < 5000）上性能优于 O(n²) 算法，且代码简单、原地排序。

public static void shellSort(int[] arr) {
int n = arr.length;
// Knuth间隔序列: 1, 4, 13, 40, 121, …
int gap = 1;
while (gap < n / 3) gap = gap * 3 + 1;

while (gap >= 1) {
// 对每个gap做插入排序
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i – gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
gap /= 3; // 缩小间隔
}
}

理解希尔排序为什么有效：第一步大间隔排序把小元素从数组末尾快速搬到前面（普通插入排序需要一个一个移动），消除了大量逆序对。到最后 gap=1 时，数组已经"几乎有序"，插入排序在近乎有序的数据上是 O(n) 的，所以最后一步非常快。

第5章 归并排序：分治的优雅

5.1 核心思想

归并排序是分治思想（Divide and Conquer）的教科书级应用：把数组对半分 → 分别排序 → 合并两个有序数组。

这个思路之所以优雅，在于它把一个O(n²)的问题分解成了两个O(n²/4)的子问题加上一个O(n)的合并，递归下来就是O(n log n)。关键洞察是：合并两个有序数组的代价是 O(n)，远低于从头排序一个无序数组。

#mermaid-svg-t2bTDNunrPRcGuFc{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-t2bTDNunrPRcGuFc .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-t2bTDNunrPRcGuFc .error-icon{fill:#552222;}#mermaid-svg-t2bTDNunrPRcGuFc .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-t2bTDNunrPRcGuFc .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-t2bTDNunrPRcGuFc .marker{fill:#333333;stroke:#333333;}#mermaid-svg-t2bTDNunrPRcGuFc .marker.cross{stroke:#333333;}#mermaid-svg-t2bTDNunrPRcGuFc svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-t2bTDNunrPRcGuFc p{margin:0;}#mermaid-svg-t2bTDNunrPRcGuFc .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-t2bTDNunrPRcGuFc .cluster-label text{fill:#333;}#mermaid-svg-t2bTDNunrPRcGuFc .cluster-label span{color:#333;}#mermaid-svg-t2bTDNunrPRcGuFc .cluster-label span p{background-color:transparent;}#mermaid-svg-t2bTDNunrPRcGuFc .label text,#mermaid-svg-t2bTDNunrPRcGuFc span{fill:#333;color:#333;}#mermaid-svg-t2bTDNunrPRcGuFc .node rect,#mermaid-svg-t2bTDNunrPRcGuFc .node circle,#mermaid-svg-t2bTDNunrPRcGuFc .node ellipse,#mermaid-svg-t2bTDNunrPRcGuFc .node polygon,#mermaid-svg-t2bTDNunrPRcGuFc .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-t2bTDNunrPRcGuFc .rough-node .label text,#mermaid-svg-t2bTDNunrPRcGuFc .node .label text,#mermaid-svg-t2bTDNunrPRcGuFc .image-shape .label,#mermaid-svg-t2bTDNunrPRcGuFc .icon-shape .label{text-anchor:middle;}#mermaid-svg-t2bTDNunrPRcGuFc .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-t2bTDNunrPRcGuFc .rough-node .label,#mermaid-svg-t2bTDNunrPRcGuFc .node .label,#mermaid-svg-t2bTDNunrPRcGuFc .image-shape .label,#mermaid-svg-t2bTDNunrPRcGuFc .icon-shape .label{text-align:center;}#mermaid-svg-t2bTDNunrPRcGuFc .node.clickable{cursor:pointer;}#mermaid-svg-t2bTDNunrPRcGuFc .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-t2bTDNunrPRcGuFc .arrowheadPath{fill:#333333;}#mermaid-svg-t2bTDNunrPRcGuFc .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-t2bTDNunrPRcGuFc .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-t2bTDNunrPRcGuFc .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-t2bTDNunrPRcGuFc .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-t2bTDNunrPRcGuFc .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-t2bTDNunrPRcGuFc .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-t2bTDNunrPRcGuFc .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-t2bTDNunrPRcGuFc .cluster text{fill:#333;}#mermaid-svg-t2bTDNunrPRcGuFc .cluster span{color:#333;}#mermaid-svg-t2bTDNunrPRcGuFc div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-t2bTDNunrPRcGuFc .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-t2bTDNunrPRcGuFc rect.text{fill:none;stroke-width:0;}#mermaid-svg-t2bTDNunrPRcGuFc .icon-shape,#mermaid-svg-t2bTDNunrPRcGuFc .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-t2bTDNunrPRcGuFc .icon-shape p,#mermaid-svg-t2bTDNunrPRcGuFc .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-t2bTDNunrPRcGuFc .icon-shape .label rect,#mermaid-svg-t2bTDNunrPRcGuFc .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-t2bTDNunrPRcGuFc .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-t2bTDNunrPRcGuFc .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-t2bTDNunrPRcGuFc :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

归并排序分治过程 [8,3,5,1,7,2,6,4]

[8,3,5,1,7,2,6,4]

[8,3,5,1]

[7,2,6,4]

[8,3]

[5,1]

[7,2]

[6,4]

[3,8]

[1,5]

[2,7]

[4,6]

[1,3,5,8]

[2,4,6,7]

[1,2,3,4,5,6,7,8]

图5-1：归并排序分治树——自顶向下对半分到单个元素，再自底向上两两合并

5.2 合并过程详解

归并排序的核心是合并（merge）操作。来看两个有序数组的合并过程：

#mermaid-svg-VQuWRhoKKtrvHRPZ{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-VQuWRhoKKtrvHRPZ .error-icon{fill:#552222;}#mermaid-svg-VQuWRhoKKtrvHRPZ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-VQuWRhoKKtrvHRPZ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .marker.cross{stroke:#333333;}#mermaid-svg-VQuWRhoKKtrvHRPZ svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-VQuWRhoKKtrvHRPZ p{margin:0;}#mermaid-svg-VQuWRhoKKtrvHRPZ .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster-label text{fill:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster-label span{color:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster-label span p{background-color:transparent;}#mermaid-svg-VQuWRhoKKtrvHRPZ .label text,#mermaid-svg-VQuWRhoKKtrvHRPZ span{fill:#333;color:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .node rect,#mermaid-svg-VQuWRhoKKtrvHRPZ .node circle,#mermaid-svg-VQuWRhoKKtrvHRPZ .node ellipse,#mermaid-svg-VQuWRhoKKtrvHRPZ .node polygon,#mermaid-svg-VQuWRhoKKtrvHRPZ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .rough-node .label text,#mermaid-svg-VQuWRhoKKtrvHRPZ .node .label text,#mermaid-svg-VQuWRhoKKtrvHRPZ .image-shape .label,#mermaid-svg-VQuWRhoKKtrvHRPZ .icon-shape .label{text-anchor:middle;}#mermaid-svg-VQuWRhoKKtrvHRPZ .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .rough-node .label,#mermaid-svg-VQuWRhoKKtrvHRPZ .node .label,#mermaid-svg-VQuWRhoKKtrvHRPZ .image-shape .label,#mermaid-svg-VQuWRhoKKtrvHRPZ .icon-shape .label{text-align:center;}#mermaid-svg-VQuWRhoKKtrvHRPZ .node.clickable{cursor:pointer;}#mermaid-svg-VQuWRhoKKtrvHRPZ .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .arrowheadPath{fill:#333333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-VQuWRhoKKtrvHRPZ .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-VQuWRhoKKtrvHRPZ .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-VQuWRhoKKtrvHRPZ .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster text{fill:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ .cluster span{color:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-VQuWRhoKKtrvHRPZ .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-VQuWRhoKKtrvHRPZ rect.text{fill:none;stroke-width:0;}#mermaid-svg-VQuWRhoKKtrvHRPZ .icon-shape,#mermaid-svg-VQuWRhoKKtrvHRPZ .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-VQuWRhoKKtrvHRPZ .icon-shape p,#mermaid-svg-VQuWRhoKKtrvHRPZ .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-VQuWRhoKKtrvHRPZ .icon-shape .label rect,#mermaid-svg-VQuWRhoKKtrvHRPZ .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-VQuWRhoKKtrvHRPZ .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-VQuWRhoKKtrvHRPZ .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-VQuWRhoKKtrvHRPZ :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

merge([1,3,5,8], [2,4,6,7])

左=[1,3,5,8] 右=[2,4,6,7] 结果=[]

1≤2 → 取1 → 结果=[1]

3>2 → 取2 → 结果=[1,2]

3≤4 → 取3 → 结果=[1,2,3]

5>4 → 取4 → 结果=[1,2,3,4]

5≤6 → 取5 → 结果=[1,2,3,4,5]

8>6 → 取6 → 结果=[1,2,3,4,5,6]

8>7 → 取7 → 结果=[1,2,3,4,5,6,7]

左剩余[8] → 追加 → [1,2,3,4,5,6,7,8]

图5-2：merge操作——双指针比较头部元素，取较小者放入结果，直到一方用完再追加另一方剩余

合并的关键性质：每次比较只取走一个元素，n个元素总共比较n-1次（最后一个元素不需要比较，直接追加），所以merge的时间复杂度是 O(n)。

5.3 代码实现

5.3.1 递归版（自顶向下）

public static void mergeSort(int[] arr) {
if (arr.length <= 1) return;
int[] temp = new int[arr.length]; // 预分配辅助数组，避免重复创建
mergeSort(arr, 0, arr.length – 1, temp);
}

private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return;
int mid = left + (right – left) / 2; // 防溢出的中点计算
mergeSort(arr, left, mid, temp); // 排左半
mergeSort(arr, mid + 1, right, temp); // 排右半
merge(arr, left, mid, right, temp); // 合并两半
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 把arr[left..right]复制到temp
System.arraycopy(arr, left, temp, left, right – left + 1);

int i = left; // 左半起点
int j = mid + 1; // 右半起点
int k = left; // 写回arr的位置

while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) { // 注意 <=，保证稳定性
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 处理剩余元素（最多一方有剩余）
while (i <= mid) arr[k++] = temp[i++];
while (j <= right) arr[k++] = temp[j++];
}

为什么预分配temp数组：如果每次merge都创建新数组，会触发频繁GC，严重影响性能。预分配一个与原数组等大的temp数组，所有merge操作共用，是标准做法。

<= 保证稳定性：当左右两边有相等元素时，取左边的（temp[i] <= temp[j] 时取 temp[i]），左边元素原本就在前面，所以相对顺序不变。如果用 <，相等时取右边的，后面的元素跑到了前面，稳定性就被破坏了。

5.3.2 迭代版（自底向上）

递归有调用开销，还可以用迭代方式自底向上实现，避免递归：

public static void mergeSortIterative(int[] arr) {
int n = arr.length;
int[] temp = new int[n];
// width从1开始倍增: 1, 2, 4, 8, …
for (int width = 1; width < n; width *= 2) {
// 每两个相邻的width大小的子数组进行合并
for (int i = 0; i < n; i += 2 * width) {
int left = i;
int mid = Math.min(i + width – 1, n – 1);
int right = Math.min(i + 2 * width – 1, n – 1);
if (mid < right) {
merge(arr, left, mid, right, temp);
}
}
}
}

自底向上的思路是：先两两合并长度为1的子数组得到长度为2的有序数组，再两两合并得到长度为4的，以此类推直到整个数组有序。逻辑等价于递归版，但不使用递归栈。

5.4 复杂度推导

时间复杂度的严格推导：

归并排序的递推关系为：T(n) = 2T(n/2) + O(n)

用递归树展开：

#mermaid-svg-fvAfP3tIb1Zq0rOq{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-fvAfP3tIb1Zq0rOq .error-icon{fill:#552222;}#mermaid-svg-fvAfP3tIb1Zq0rOq .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-fvAfP3tIb1Zq0rOq .marker{fill:#333333;stroke:#333333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .marker.cross{stroke:#333333;}#mermaid-svg-fvAfP3tIb1Zq0rOq svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-fvAfP3tIb1Zq0rOq p{margin:0;}#mermaid-svg-fvAfP3tIb1Zq0rOq .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster-label text{fill:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster-label span{color:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster-label span p{background-color:transparent;}#mermaid-svg-fvAfP3tIb1Zq0rOq .label text,#mermaid-svg-fvAfP3tIb1Zq0rOq span{fill:#333;color:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .node rect,#mermaid-svg-fvAfP3tIb1Zq0rOq .node circle,#mermaid-svg-fvAfP3tIb1Zq0rOq .node ellipse,#mermaid-svg-fvAfP3tIb1Zq0rOq .node polygon,#mermaid-svg-fvAfP3tIb1Zq0rOq .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .rough-node .label text,#mermaid-svg-fvAfP3tIb1Zq0rOq .node .label text,#mermaid-svg-fvAfP3tIb1Zq0rOq .image-shape .label,#mermaid-svg-fvAfP3tIb1Zq0rOq .icon-shape .label{text-anchor:middle;}#mermaid-svg-fvAfP3tIb1Zq0rOq .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .rough-node .label,#mermaid-svg-fvAfP3tIb1Zq0rOq .node .label,#mermaid-svg-fvAfP3tIb1Zq0rOq .image-shape .label,#mermaid-svg-fvAfP3tIb1Zq0rOq .icon-shape .label{text-align:center;}#mermaid-svg-fvAfP3tIb1Zq0rOq .node.clickable{cursor:pointer;}#mermaid-svg-fvAfP3tIb1Zq0rOq .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .arrowheadPath{fill:#333333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-fvAfP3tIb1Zq0rOq .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-fvAfP3tIb1Zq0rOq .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-fvAfP3tIb1Zq0rOq .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster text{fill:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq .cluster span{color:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-fvAfP3tIb1Zq0rOq .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-fvAfP3tIb1Zq0rOq rect.text{fill:none;stroke-width:0;}#mermaid-svg-fvAfP3tIb1Zq0rOq .icon-shape,#mermaid-svg-fvAfP3tIb1Zq0rOq .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-fvAfP3tIb1Zq0rOq .icon-shape p,#mermaid-svg-fvAfP3tIb1Zq0rOq .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-fvAfP3tIb1Zq0rOq .icon-shape .label rect,#mermaid-svg-fvAfP3tIb1Zq0rOq .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-fvAfP3tIb1Zq0rOq .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-fvAfP3tIb1Zq0rOq .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-fvAfP3tIb1Zq0rOq :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

递推式展开 T(n) = 2T(n/2) + cn

每层总代价

T(n) = 2T(n/2) + cn总代价: cn

T(n/2)

T(n/2)

T(n/4)

T(n/4)

T(n/4)

T(n/4)

第0层: cn第1层: 2×c(n/2)=cn第2层: 4×c(n/4)=cn…第log₂n层: n×c(1)=cn总计: cn × (log₂n+1) = O(n log n)

图5-3：归并排序递归树复杂度推导——每层合并总代价都是cn，共log₂n+1层，总计O(n log n)

• 第0层：1次merge，代价 cn
• 第1层：2次merge，每次 cn/2，总代价 cn
• 第k层：2^k 次 merge，每次 cn/2^k，总代价 cn
• 树高 log₂n + 1 层
• 总代价：cn × (log₂n + 1) = O(n log n)

空间复杂度：O(n)，需要辅助数组。递归栈深度为 O(log n)，但 O(n) 的辅助数组是主要开销。

5.5 稳定性证明

归并排序是稳定的。

稳定性来自 merge 操作中 temp[i] <= temp[j] 的 <=：当左右两边有相等元素时，优先取左边的元素。左边元素在原数组中的位置在前面，取到结果数组后仍在前面，相对顺序不变。逐层递归都保持这个性质，最终结果稳定。

5.6 归并排序的独特优势

归并排序在实际工程中有三个其他O(n log n)排序无法替代的优势：

优势1：适合链表排序。

链表不支持随机访问，快排的partition需要随机访问，堆排需要数组索引，都不适合链表。但归并排序的merge只需要顺序遍历，天然适合链表。链表版的归并排序不需要额外空间——通过修改指针就能合并两个有序链表。

// 链表归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 快慢指针找中点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
slow.next = null; // 断开
// 递归排序两半
ListNode left = sortList(head);
right = sortList(right);
// 合并
return mergeList(left, right);
}

private ListNode mergeList(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { // <= 保证稳定
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dummy.next;
}

优势2：适合外部排序。

当数据量远超内存时（如100GB文件排序），无法全部加载到内存。归并排序天然适合外部排序：先把数据分块加载到内存排序，写入临时文件，再多路归并。

#mermaid-svg-G3XSY9xuAV7hlq1W{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-G3XSY9xuAV7hlq1W .error-icon{fill:#552222;}#mermaid-svg-G3XSY9xuAV7hlq1W .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-G3XSY9xuAV7hlq1W .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-G3XSY9xuAV7hlq1W .marker{fill:#333333;stroke:#333333;}#mermaid-svg-G3XSY9xuAV7hlq1W .marker.cross{stroke:#333333;}#mermaid-svg-G3XSY9xuAV7hlq1W svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-G3XSY9xuAV7hlq1W p{margin:0;}#mermaid-svg-G3XSY9xuAV7hlq1W .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster-label text{fill:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster-label span{color:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster-label span p{background-color:transparent;}#mermaid-svg-G3XSY9xuAV7hlq1W .label text,#mermaid-svg-G3XSY9xuAV7hlq1W span{fill:#333;color:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W .node rect,#mermaid-svg-G3XSY9xuAV7hlq1W .node circle,#mermaid-svg-G3XSY9xuAV7hlq1W .node ellipse,#mermaid-svg-G3XSY9xuAV7hlq1W .node polygon,#mermaid-svg-G3XSY9xuAV7hlq1W .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-G3XSY9xuAV7hlq1W .rough-node .label text,#mermaid-svg-G3XSY9xuAV7hlq1W .node .label text,#mermaid-svg-G3XSY9xuAV7hlq1W .image-shape .label,#mermaid-svg-G3XSY9xuAV7hlq1W .icon-shape .label{text-anchor:middle;}#mermaid-svg-G3XSY9xuAV7hlq1W .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-G3XSY9xuAV7hlq1W .rough-node .label,#mermaid-svg-G3XSY9xuAV7hlq1W .node .label,#mermaid-svg-G3XSY9xuAV7hlq1W .image-shape .label,#mermaid-svg-G3XSY9xuAV7hlq1W .icon-shape .label{text-align:center;}#mermaid-svg-G3XSY9xuAV7hlq1W .node.clickable{cursor:pointer;}#mermaid-svg-G3XSY9xuAV7hlq1W .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-G3XSY9xuAV7hlq1W .arrowheadPath{fill:#333333;}#mermaid-svg-G3XSY9xuAV7hlq1W .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-G3XSY9xuAV7hlq1W .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-G3XSY9xuAV7hlq1W .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-G3XSY9xuAV7hlq1W .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-G3XSY9xuAV7hlq1W .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-G3XSY9xuAV7hlq1W .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster text{fill:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W .cluster span{color:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-G3XSY9xuAV7hlq1W .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-G3XSY9xuAV7hlq1W rect.text{fill:none;stroke-width:0;}#mermaid-svg-G3XSY9xuAV7hlq1W .icon-shape,#mermaid-svg-G3XSY9xuAV7hlq1W .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-G3XSY9xuAV7hlq1W .icon-shape p,#mermaid-svg-G3XSY9xuAV7hlq1W .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-G3XSY9xuAV7hlq1W .icon-shape .label rect,#mermaid-svg-G3XSY9xuAV7hlq1W .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-G3XSY9xuAV7hlq1W .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-G3XSY9xuAV7hlq1W .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-G3XSY9xuAV7hlq1W :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

外部归并排序

100GB文件

分块100MB读入内存

内存排序→写入1000个临时文件

k路归并（用堆维护k个文件的最小值）

100GB有序文件

图5-4：外部归并排序——大文件分块内存排序，然后多路归并。归并是外部排序的标准方案

优势3：稳定且性能可预测。

归并排序的最好、平均、最坏都是 O(n log n)，没有最坏退化问题。对于需要稳定排序且要求性能可预测的场景（如数据库排序），归并排序是首选。

5.7 归并排序 vs 快速排序

这是面试和工程中最常被问到的问题：为什么快排平均O(n log n)但实际比归并快，而归并最坏也是O(n log n)反而用得少？

答案将在第6章详细解答。

第6章 快速排序：为什么它是实际最快的

6.1 核心思想

快速排序的核心思想是 partition（分区）：选一个基准值（pivot），把数组分成"小于pivot"和"大于pivot"两部分，然后对两部分递归排序。

与归并排序的对比：

• 归并排序：先递归排序，再合并（合并是主要工作）
• 快速排序：先分区，再递归排序（分区是主要工作）

快排的巧妙之处在于：分区完成后，pivot已经在最终位置了，不需要像归并那样再合并。这是因为分区的定义保证了左边全部 ≤ pivot，右边全部 ≥ pivot，pivot的位置不会变了。

6.2 Partition 详解

快排的灵魂是 partition 函数。最经典的是 Lomuto 分区方案：

#mermaid-svg-3ThULh5NSMuP4b2H{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-3ThULh5NSMuP4b2H .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-3ThULh5NSMuP4b2H .error-icon{fill:#552222;}#mermaid-svg-3ThULh5NSMuP4b2H .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-3ThULh5NSMuP4b2H .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-3ThULh5NSMuP4b2H .marker{fill:#333333;stroke:#333333;}#mermaid-svg-3ThULh5NSMuP4b2H .marker.cross{stroke:#333333;}#mermaid-svg-3ThULh5NSMuP4b2H svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-3ThULh5NSMuP4b2H p{margin:0;}#mermaid-svg-3ThULh5NSMuP4b2H .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-3ThULh5NSMuP4b2H .cluster-label text{fill:#333;}#mermaid-svg-3ThULh5NSMuP4b2H .cluster-label span{color:#333;}#mermaid-svg-3ThULh5NSMuP4b2H .cluster-label span p{background-color:transparent;}#mermaid-svg-3ThULh5NSMuP4b2H .label text,#mermaid-svg-3ThULh5NSMuP4b2H span{fill:#333;color:#333;}#mermaid-svg-3ThULh5NSMuP4b2H .node rect,#mermaid-svg-3ThULh5NSMuP4b2H .node circle,#mermaid-svg-3ThULh5NSMuP4b2H .node ellipse,#mermaid-svg-3ThULh5NSMuP4b2H .node polygon,#mermaid-svg-3ThULh5NSMuP4b2H .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-3ThULh5NSMuP4b2H .rough-node .label text,#mermaid-svg-3ThULh5NSMuP4b2H .node .label text,#mermaid-svg-3ThULh5NSMuP4b2H .image-shape .label,#mermaid-svg-3ThULh5NSMuP4b2H .icon-shape .label{text-anchor:middle;}#mermaid-svg-3ThULh5NSMuP4b2H .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-3ThULh5NSMuP4b2H .rough-node .label,#mermaid-svg-3ThULh5NSMuP4b2H .node .label,#mermaid-svg-3ThULh5NSMuP4b2H .image-shape .label,#mermaid-svg-3ThULh5NSMuP4b2H .icon-shape .label{text-align:center;}#mermaid-svg-3ThULh5NSMuP4b2H .node.clickable{cursor:pointer;}#mermaid-svg-3ThULh5NSMuP4b2H .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-3ThULh5NSMuP4b2H .arrowheadPath{fill:#333333;}#mermaid-svg-3ThULh5NSMuP4b2H .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-3ThULh5NSMuP4b2H .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-3ThULh5NSMuP4b2H .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3ThULh5NSMuP4b2H .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-3ThULh5NSMuP4b2H .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3ThULh5NSMuP4b2H .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-3ThULh5NSMuP4b2H .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-3ThULh5NSMuP4b2H .cluster text{fill:#333;}#mermaid-svg-3ThULh5NSMuP4b2H .cluster span{color:#333;}#mermaid-svg-3ThULh5NSMuP4b2H div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-3ThULh5NSMuP4b2H .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-3ThULh5NSMuP4b2H rect.text{fill:none;stroke-width:0;}#mermaid-svg-3ThULh5NSMuP4b2H .icon-shape,#mermaid-svg-3ThULh5NSMuP4b2H .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-3ThULh5NSMuP4b2H .icon-shape p,#mermaid-svg-3ThULh5NSMuP4b2H .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-3ThULh5NSMuP4b2H .icon-shape .label rect,#mermaid-svg-3ThULh5NSMuP4b2H .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-3ThULh5NSMuP4b2H .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-3ThULh5NSMuP4b2H .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-3ThULh5NSMuP4b2H :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

Lomuto Partition pivot=4, arr=[5,3,8,1,6,2,7,4]

初始: i=-1, j从0到6扫描

j=0: arr[0]=5 > 4, 不动, i=-1

j=1: arr[1]=3 ≤ 4, i=0, 交换arr[0]↔arr[1] → [3,5,8,1,6,2,7,4]

j=2: arr[2]=8 > 4, 不动, i=0

j=3: arr[3]=1 ≤ 4, i=1, 交换arr[1]↔arr[3] → [3,1,8,5,6,2,7,4]

j=4: arr[4]=6 > 4, 不动, i=1

j=5: arr[5]=2 ≤ 4, i=2, 交换arr[2]↔arr[5] → [3,1,2,5,6,8,7,4]

j=6: arr[6]=7 > 4, 不动, i=2

扫描完毕: 交换arr[i+1]↔arr[7] → [3,1,2,4,6,8,7,5]

pivot在位置3, 左边[3,1,2]全≤4, 右边[6,8,7,5]全>4

图6-1：Lomuto Partition完整过程——i维护"≤pivot区域"的右边界，j扫描每个元素，遇到小的就纳入区域

Lomuto Partition 的逻辑：

// 返回pivot最终位置，arr[lo..hi]被分为 ≤pivot 和 >pivot 两部分
private static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi]; // 选最后一个元素作为pivot
int i = lo – 1; // i指向"≤pivot区域"的最后一个元素
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j); // 把小元素交换到≤区域
}
}
swap(arr, i + 1, hi); // pivot放到中间
return i + 1; // 返回pivot最终位置
}

为什么这个分区能正确工作：变量 i 维护了"已知 ≤ pivot 的区域"的右边界。变量 j 从左向右扫描，每当发现一个 ≤ pivot 的元素，就扩大 ≤ 区域（i++）并把该元素交换进来。扫描结束后，arr[lo..i] 全部 ≤ pivot，arr[i+1..hi-1] 全部 > pivot，最后把 pivot 放到 i+1 位置，它就到了正确的最终位置。

6.3 完整快排实现

public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length – 1);
}

private static void quickSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int p = partition(arr, lo, hi); // 分区，p是pivot最终位置
quickSort(arr, lo, p – 1); // 排左半
quickSort(arr, p + 1, hi); // 排右半
// 注意：pivot位置p不需要再处理，它已经在最终位置了
}

快排的递归结构与归并不同：归并是"先排后合"，快排是"先分后排不合"。归并的merge在递归之后，快排的partition在递归之前。

6.4 Hoare 分区方案

Lomuto 方案简单但效率不是最高——它用 arr[hi] 作 pivot 并只做单向扫描。Hoare 原始方案用双指针从两端向中间走，交换逆序对，平均交换次数更少：

private static int partitionHoare(int[] arr, int lo, int hi) {
int pivot = arr[lo + (hi – lo) / 2]; // 中间元素作pivot
int i = lo – 1, j = hi + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // 左指针找≥pivot的
do { j—; } while (arr[j] > pivot); // 右指针找≤pivot的
if (i >= j) return j; // 指针相遇，返回分界点
swap(arr, i, j); // 交换逆序对
}
}

Hoare 方案的特点：用 do-while 而非 while，保证指针至少移动一步（避免死循环）；返回的是 j 而非 i+1，分区点不一定是pivot的最终位置，但保证 arr[lo..j] ≤ arr[j+1..hi]，递归时 quickSort(arr, lo, j) 和 quickSort(arr, j+1, hi)。

两种方案的对比：

6.5 复杂度分析

快排的复杂度取决于 pivot 的选择质量——即分区是否平衡。

最好情况：每次 pivot 恰好是中位数，把数组等分两半。

T(n) = 2T(n/2) + O(n) → O(n log n)

与归并排序相同的递推式，但常数因子更小（partition 比 merge 简单）。

最坏情况：每次 pivot 是最大或最小值，分区极度不平衡（一边0个，另一边n-1个）。

T(n) = T(n-1) + O(n) → O(n²)

这发生在数组已有序且总是选第一个或最后一个元素作 pivot 的场景。

平均情况：O(n log n)。可以用概率分析证明，即使pivot随机选，期望比较次数约为 2n ln n ≈ 1.39 n log₂ n，比归并排序的 n log₂ n 稍多，但常数因子更小。

#mermaid-svg-B5rm8Vnlud65WqqL{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-B5rm8Vnlud65WqqL .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-B5rm8Vnlud65WqqL .error-icon{fill:#552222;}#mermaid-svg-B5rm8Vnlud65WqqL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-B5rm8Vnlud65WqqL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-B5rm8Vnlud65WqqL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-B5rm8Vnlud65WqqL .marker.cross{stroke:#333333;}#mermaid-svg-B5rm8Vnlud65WqqL svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-B5rm8Vnlud65WqqL p{margin:0;}#mermaid-svg-B5rm8Vnlud65WqqL .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-B5rm8Vnlud65WqqL .cluster-label text{fill:#333;}#mermaid-svg-B5rm8Vnlud65WqqL .cluster-label span{color:#333;}#mermaid-svg-B5rm8Vnlud65WqqL .cluster-label span p{background-color:transparent;}#mermaid-svg-B5rm8Vnlud65WqqL .label text,#mermaid-svg-B5rm8Vnlud65WqqL span{fill:#333;color:#333;}#mermaid-svg-B5rm8Vnlud65WqqL .node rect,#mermaid-svg-B5rm8Vnlud65WqqL .node circle,#mermaid-svg-B5rm8Vnlud65WqqL .node ellipse,#mermaid-svg-B5rm8Vnlud65WqqL .node polygon,#mermaid-svg-B5rm8Vnlud65WqqL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-B5rm8Vnlud65WqqL .rough-node .label text,#mermaid-svg-B5rm8Vnlud65WqqL .node .label text,#mermaid-svg-B5rm8Vnlud65WqqL .image-shape .label,#mermaid-svg-B5rm8Vnlud65WqqL .icon-shape .label{text-anchor:middle;}#mermaid-svg-B5rm8Vnlud65WqqL .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-B5rm8Vnlud65WqqL .rough-node .label,#mermaid-svg-B5rm8Vnlud65WqqL .node .label,#mermaid-svg-B5rm8Vnlud65WqqL .image-shape .label,#mermaid-svg-B5rm8Vnlud65WqqL .icon-shape .label{text-align:center;}#mermaid-svg-B5rm8Vnlud65WqqL .node.clickable{cursor:pointer;}#mermaid-svg-B5rm8Vnlud65WqqL .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-B5rm8Vnlud65WqqL .arrowheadPath{fill:#333333;}#mermaid-svg-B5rm8Vnlud65WqqL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-B5rm8Vnlud65WqqL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-B5rm8Vnlud65WqqL .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-B5rm8Vnlud65WqqL .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-B5rm8Vnlud65WqqL .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-B5rm8Vnlud65WqqL .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-B5rm8Vnlud65WqqL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-B5rm8Vnlud65WqqL .cluster text{fill:#333;}#mermaid-svg-B5rm8Vnlud65WqqL .cluster span{color:#333;}#mermaid-svg-B5rm8Vnlud65WqqL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-B5rm8Vnlud65WqqL .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-B5rm8Vnlud65WqqL rect.text{fill:none;stroke-width:0;}#mermaid-svg-B5rm8Vnlud65WqqL .icon-shape,#mermaid-svg-B5rm8Vnlud65WqqL .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-B5rm8Vnlud65WqqL .icon-shape p,#mermaid-svg-B5rm8Vnlud65WqqL .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-B5rm8Vnlud65WqqL .icon-shape .label rect,#mermaid-svg-B5rm8Vnlud65WqqL .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-B5rm8Vnlud65WqqL .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-B5rm8Vnlud65WqqL .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-B5rm8Vnlud65WqqL :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

pivot选择对快排复杂度的影响

每次等分

极度不平衡

期望平衡

pivot恰好是中位数

T(n) = 2T(n/2) + O(n)= O(n log n) ✓

pivot是最值

T(n) = T(n-1) + O(n)= O(n²) ✗

pivot随机选

期望比较 ≈ 2n ln n= O(n log n) ✓

图6-2：pivot选择质量直接决定快排性能——平衡分区得O(n log n)，极不平衡退化为O(n²)

6.6 避免最坏情况：Pivot 优化策略

由于最坏情况是O(n²)，工程中必须优化pivot选择。三种主要策略：

6.6.1 随机选 Pivot

private static int partitionRandom(int[] arr, int lo, int hi) {
// 随机选一个元素与arr[hi]交换，再用Lomuto方案
int randIdx = lo + new Random().nextInt(hi – lo + 1);
swap(arr, randIdx, hi);
return partition(arr, lo, hi); // 标准Lomuto
}

随机化后，没有任何特定输入能稳定触发最坏情况。期望复杂度为 O(n log n)，最坏情况概率极低。

6.6.2 三数取中（Median-of-Three）

private static int medianOfThree(int[] arr, int lo, int hi) {
int mid = lo + (hi – lo) / 2;
// 排序arr[lo], arr[mid], arr[hi]，取中位数放到arr[hi]
if (arr[lo] > arr[mid]) swap(arr, lo, mid);
if (arr[lo] > arr[hi]) swap(arr, lo, hi);
if (arr[mid] > arr[hi]) swap(arr, mid, hi);
// 此时arr[mid] ≤ arr[hi]，arr[lo] ≤ arr[hi]
// 把中位数arr[mid]换到arr[hi]作pivot
swap(arr, mid, hi);
return partition(arr, lo, hi);
}

三数取中对已有序/逆序输入特别有效——这两种输入是朴素快排的最坏情况，但三数取中能直接选中中位数，变成最好情况。

6.6.3 IntroSort（内省排序）

C++ STL 使用的方法：快排递归深度超过 2log₂n 时切换为堆排，保证最坏O(n log n)。这将在第9章详细讲解。

6.7 快排为什么不稳定

快速排序是不稳定的。

不稳定的原因是 partition 中的交换操作可能跨越相等元素。以 Lomuto 方案为例：

数组 [3a, 3b, 2]，pivot = 2（arr[2]）：

j=0: arr[0]=3 > 2, 不动, i=-1
j=1: arr[1]=3 > 2, 不动, i=-1
扫描完毕: swap(arr[0], arr[2]) → [2, 3b, 3a]

3a 原来在 3b 前面，交换后 3a 跑到了 3b 后面。Hoare 方案同样存在这个问题——双指针交换时可能跨过相等元素。

要使快排稳定，需要 O(n) 额外空间（用辅助数组做稳定分区），但这样就失去了快排原地排序的优势，不如直接用归并排序。

6.8 为什么快排实际最快

这是本文最核心的问题。快排的平均比较次数（1.39 n log₂ n）比归并（n log₂ n）还多，为什么实际运行更快？

原因1：缓存友好（最重要）。

快排的 partition 是顺序扫描数组（j 从 lo 到 hi），CPU 缓存预取命中率高。归并排序的 merge 需要同时读两个子数组并写回，访问模式跳跃，缓存不友好。在现代CPU上，缓存命中率对性能的影响远大于比较次数的细微差异。

原因2：常数因子小。

partition 内部只有一次比较和一次自增（if arr[j] <= pivot + i++），非常精简。归并的 merge 需要两次比较（temp[i] <= temp[j] 加上边界检查）和数组拷贝（System.arraycopy），开销更大。

原因3：原地排序，不分配额外空间。

归并排序需要 O(n) 辅助数组，分配和释放内存有开销。快排原地排序，只有递归栈 O(log n) 的空间。

原因4：分区后子问题可能很小。

快排在分区后，如果pivot选得好，很多元素一次就到位了。加上小区间切换插入排序，实际递归深度比理论值浅。

#mermaid-svg-b1WHpM2vcnZ9uniS{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-b1WHpM2vcnZ9uniS .error-icon{fill:#552222;}#mermaid-svg-b1WHpM2vcnZ9uniS .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-b1WHpM2vcnZ9uniS .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-b1WHpM2vcnZ9uniS .marker{fill:#333333;stroke:#333333;}#mermaid-svg-b1WHpM2vcnZ9uniS .marker.cross{stroke:#333333;}#mermaid-svg-b1WHpM2vcnZ9uniS svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-b1WHpM2vcnZ9uniS p{margin:0;}#mermaid-svg-b1WHpM2vcnZ9uniS .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster-label text{fill:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster-label span{color:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster-label span p{background-color:transparent;}#mermaid-svg-b1WHpM2vcnZ9uniS .label text,#mermaid-svg-b1WHpM2vcnZ9uniS span{fill:#333;color:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS .node rect,#mermaid-svg-b1WHpM2vcnZ9uniS .node circle,#mermaid-svg-b1WHpM2vcnZ9uniS .node ellipse,#mermaid-svg-b1WHpM2vcnZ9uniS .node polygon,#mermaid-svg-b1WHpM2vcnZ9uniS .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-b1WHpM2vcnZ9uniS .rough-node .label text,#mermaid-svg-b1WHpM2vcnZ9uniS .node .label text,#mermaid-svg-b1WHpM2vcnZ9uniS .image-shape .label,#mermaid-svg-b1WHpM2vcnZ9uniS .icon-shape .label{text-anchor:middle;}#mermaid-svg-b1WHpM2vcnZ9uniS .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-b1WHpM2vcnZ9uniS .rough-node .label,#mermaid-svg-b1WHpM2vcnZ9uniS .node .label,#mermaid-svg-b1WHpM2vcnZ9uniS .image-shape .label,#mermaid-svg-b1WHpM2vcnZ9uniS .icon-shape .label{text-align:center;}#mermaid-svg-b1WHpM2vcnZ9uniS .node.clickable{cursor:pointer;}#mermaid-svg-b1WHpM2vcnZ9uniS .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-b1WHpM2vcnZ9uniS .arrowheadPath{fill:#333333;}#mermaid-svg-b1WHpM2vcnZ9uniS .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-b1WHpM2vcnZ9uniS .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-b1WHpM2vcnZ9uniS .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-b1WHpM2vcnZ9uniS .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-b1WHpM2vcnZ9uniS .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-b1WHpM2vcnZ9uniS .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster text{fill:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS .cluster span{color:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-b1WHpM2vcnZ9uniS .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-b1WHpM2vcnZ9uniS rect.text{fill:none;stroke-width:0;}#mermaid-svg-b1WHpM2vcnZ9uniS .icon-shape,#mermaid-svg-b1WHpM2vcnZ9uniS .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-b1WHpM2vcnZ9uniS .icon-shape p,#mermaid-svg-b1WHpM2vcnZ9uniS .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-b1WHpM2vcnZ9uniS .icon-shape .label rect,#mermaid-svg-b1WHpM2vcnZ9uniS .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-b1WHpM2vcnZ9uniS .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-b1WHpM2vcnZ9uniS .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-b1WHpM2vcnZ9uniS :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

快排实际最快的原因

快排 vs 归并比较次数: 1.39n·log₂n vs n·log₂n快排多39%，但实际更快

原因1: 缓存友好顺序扫描 vs 跳跃访问

原因2: 常数因子小partition比merge简单

原因3: 原地排序无O(n)辅助数组分配

原因4: 分区即定位很多元素一步到位

图6-3：快排虽然比较次数比归并多39%，但凭借缓存友好和低常数因子实际更快

6.9 非递归实现

快排也可以用栈模拟递归，避免递归栈溢出：

public static void quickSortIterative(int[] arr) {
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{0, arr.length – 1});
while (!stack.isEmpty()) {
int[] range = stack.pop();
int lo = range[0], hi = range[1];
if (lo >= hi) continue;
int p = partition(arr, lo, hi);
// 先处理大区间（用尾递归优化栈深度）
if (p – lo > hi – p) {
stack.push(new int[]{lo, p – 1});
stack.push(new int[]{p + 1, hi});
} else {
stack.push(new int[]{p + 1, hi});
stack.push(new int[]{lo, p – 1});
}
}
}

工程中的优化技巧：尾递归消除。始终先处理较小的子区间，较大的子区间用循环处理，保证栈深度不超过 O(log n)：

private static void quickSortTailOpt(int[] arr, int lo, int hi) {
while (lo < hi) {
int p = partition(arr, lo, hi);
if (p – lo < hi – p) {
quickSortTailOpt(arr, lo, p – 1); // 递归处理小半
lo = p + 1; // 循环处理大半（尾递归消除）
} else {
quickSortTailOpt(arr, p + 1, hi);
hi = p – 1;
}
}
}

这样栈深度最多 O(log n)，即使最坏情况下也不会栈溢出。

第7章 堆排序：优先队列的排序

7.1 核心思想

堆排序利用**堆（Heap）**这种数据结构来排序：先建一个大顶堆，然后反复取出堆顶（最大值）放到数组末尾，再调整堆。

理解堆排序的前提是理解堆。堆是一棵完全二叉树，用数组存储（不需要指针），满足：

• 大顶堆：每个节点的值 ≥ 其子节点的值
• 小顶堆：每个节点的值 ≤ 其子节点的值

数组与树的映射关系：对于节点 i，左子节点 2i+1，右子节点 2i+2，父节点 (i-1)/2。

#mermaid-svg-06XsuJFNbdWUQbPL{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-06XsuJFNbdWUQbPL .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-06XsuJFNbdWUQbPL .error-icon{fill:#552222;}#mermaid-svg-06XsuJFNbdWUQbPL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-06XsuJFNbdWUQbPL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-06XsuJFNbdWUQbPL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-06XsuJFNbdWUQbPL .marker.cross{stroke:#333333;}#mermaid-svg-06XsuJFNbdWUQbPL svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-06XsuJFNbdWUQbPL p{margin:0;}#mermaid-svg-06XsuJFNbdWUQbPL .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-06XsuJFNbdWUQbPL .cluster-label text{fill:#333;}#mermaid-svg-06XsuJFNbdWUQbPL .cluster-label span{color:#333;}#mermaid-svg-06XsuJFNbdWUQbPL .cluster-label span p{background-color:transparent;}#mermaid-svg-06XsuJFNbdWUQbPL .label text,#mermaid-svg-06XsuJFNbdWUQbPL span{fill:#333;color:#333;}#mermaid-svg-06XsuJFNbdWUQbPL .node rect,#mermaid-svg-06XsuJFNbdWUQbPL .node circle,#mermaid-svg-06XsuJFNbdWUQbPL .node ellipse,#mermaid-svg-06XsuJFNbdWUQbPL .node polygon,#mermaid-svg-06XsuJFNbdWUQbPL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-06XsuJFNbdWUQbPL .rough-node .label text,#mermaid-svg-06XsuJFNbdWUQbPL .node .label text,#mermaid-svg-06XsuJFNbdWUQbPL .image-shape .label,#mermaid-svg-06XsuJFNbdWUQbPL .icon-shape .label{text-anchor:middle;}#mermaid-svg-06XsuJFNbdWUQbPL .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-06XsuJFNbdWUQbPL .rough-node .label,#mermaid-svg-06XsuJFNbdWUQbPL .node .label,#mermaid-svg-06XsuJFNbdWUQbPL .image-shape .label,#mermaid-svg-06XsuJFNbdWUQbPL .icon-shape .label{text-align:center;}#mermaid-svg-06XsuJFNbdWUQbPL .node.clickable{cursor:pointer;}#mermaid-svg-06XsuJFNbdWUQbPL .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-06XsuJFNbdWUQbPL .arrowheadPath{fill:#333333;}#mermaid-svg-06XsuJFNbdWUQbPL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-06XsuJFNbdWUQbPL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-06XsuJFNbdWUQbPL .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-06XsuJFNbdWUQbPL .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-06XsuJFNbdWUQbPL .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-06XsuJFNbdWUQbPL .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-06XsuJFNbdWUQbPL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-06XsuJFNbdWUQbPL .cluster text{fill:#333;}#mermaid-svg-06XsuJFNbdWUQbPL .cluster span{color:#333;}#mermaid-svg-06XsuJFNbdWUQbPL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-06XsuJFNbdWUQbPL .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-06XsuJFNbdWUQbPL rect.text{fill:none;stroke-width:0;}#mermaid-svg-06XsuJFNbdWUQbPL .icon-shape,#mermaid-svg-06XsuJFNbdWUQbPL .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-06XsuJFNbdWUQbPL .icon-shape p,#mermaid-svg-06XsuJFNbdWUQbPL .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-06XsuJFNbdWUQbPL .icon-shape .label rect,#mermaid-svg-06XsuJFNbdWUQbPL .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-06XsuJFNbdWUQbPL .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-06XsuJFNbdWUQbPL .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-06XsuJFNbdWUQbPL :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

大顶堆的数组表示

数组视图

树形视图

索引: 0 1 2 3 4 5 6

50

30

40

10

20

35

15

值: 50 30 40 10 20 35 15

图7-1：大顶堆的树形与数组映射——节点i的左子为2i+1，右子为2i+2，父为(i-1)/2

7.2 堆的核心操作：Sift Down

堆排序的核心是 sift down（下沉） 操作：将一个可能违反堆性质的节点向下调整到正确位置。

#mermaid-svg-modNDZ3VvJdvgByy{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-modNDZ3VvJdvgByy .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-modNDZ3VvJdvgByy .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-modNDZ3VvJdvgByy .error-icon{fill:#552222;}#mermaid-svg-modNDZ3VvJdvgByy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-modNDZ3VvJdvgByy .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-modNDZ3VvJdvgByy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-modNDZ3VvJdvgByy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-modNDZ3VvJdvgByy .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-modNDZ3VvJdvgByy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-modNDZ3VvJdvgByy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-modNDZ3VvJdvgByy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-modNDZ3VvJdvgByy .marker.cross{stroke:#333333;}#mermaid-svg-modNDZ3VvJdvgByy svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-modNDZ3VvJdvgByy p{margin:0;}#mermaid-svg-modNDZ3VvJdvgByy .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-modNDZ3VvJdvgByy .cluster-label text{fill:#333;}#mermaid-svg-modNDZ3VvJdvgByy .cluster-label span{color:#333;}#mermaid-svg-modNDZ3VvJdvgByy .cluster-label span p{background-color:transparent;}#mermaid-svg-modNDZ3VvJdvgByy .label text,#mermaid-svg-modNDZ3VvJdvgByy span{fill:#333;color:#333;}#mermaid-svg-modNDZ3VvJdvgByy .node rect,#mermaid-svg-modNDZ3VvJdvgByy .node circle,#mermaid-svg-modNDZ3VvJdvgByy .node ellipse,#mermaid-svg-modNDZ3VvJdvgByy .node polygon,#mermaid-svg-modNDZ3VvJdvgByy .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-modNDZ3VvJdvgByy .rough-node .label text,#mermaid-svg-modNDZ3VvJdvgByy .node .label text,#mermaid-svg-modNDZ3VvJdvgByy .image-shape .label,#mermaid-svg-modNDZ3VvJdvgByy .icon-shape .label{text-anchor:middle;}#mermaid-svg-modNDZ3VvJdvgByy .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-modNDZ3VvJdvgByy .rough-node .label,#mermaid-svg-modNDZ3VvJdvgByy .node .label,#mermaid-svg-modNDZ3VvJdvgByy .image-shape .label,#mermaid-svg-modNDZ3VvJdvgByy .icon-shape .label{text-align:center;}#mermaid-svg-modNDZ3VvJdvgByy .node.clickable{cursor:pointer;}#mermaid-svg-modNDZ3VvJdvgByy .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-modNDZ3VvJdvgByy .arrowheadPath{fill:#333333;}#mermaid-svg-modNDZ3VvJdvgByy .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-modNDZ3VvJdvgByy .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-modNDZ3VvJdvgByy .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-modNDZ3VvJdvgByy .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-modNDZ3VvJdvgByy .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-modNDZ3VvJdvgByy .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-modNDZ3VvJdvgByy .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-modNDZ3VvJdvgByy .cluster text{fill:#333;}#mermaid-svg-modNDZ3VvJdvgByy .cluster span{color:#333;}#mermaid-svg-modNDZ3VvJdvgByy div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-modNDZ3VvJdvgByy .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-modNDZ3VvJdvgByy rect.text{fill:none;stroke-width:0;}#mermaid-svg-modNDZ3VvJdvgByy .icon-shape,#mermaid-svg-modNDZ3VvJdvgByy .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-modNDZ3VvJdvgByy .icon-shape p,#mermaid-svg-modNDZ3VvJdvgByy .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-modNDZ3VvJdvgByy .icon-shape .label rect,#mermaid-svg-modNDZ3VvJdvgByy .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-modNDZ3VvJdvgByy .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-modNDZ3VvJdvgByy .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-modNDZ3VvJdvgByy :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

sift down 示例：调整节点20（索引4）

大顶堆被破坏: 父20 < 子35 需要下沉

20与较大的子节点35比较20<35, 交换

20在原35的位置(索引5)无子节点, 下沉结束

调整后: 50→30→40→10→35→20→15 恢复大顶堆性质

图7-2：sift down 操作——将违反堆性质的节点与其较大的子节点交换，直到恢复堆性质或到达叶子

// 将arr[i]下沉到正确位置，堆范围[0, heapSize)
private static void siftDown(int[] arr, int i, int heapSize) {
while (true) {
int left = 2 * i + 1; // 左子
int right = 2 * i + 2; // 右子
int largest = i; // 假设自己最大

if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest == i) break; // 自己已经最大，结束

swap(arr, i, largest); // 与较大的子节点交换
i = largest; // 继续下沉
}
}

7.3 建堆过程

堆排序第一步是建堆。从最后一个非叶子节点开始，从右向左、从下向上逐个执行 sift down。

为什么从最后一个非叶子节点开始：叶子节点没有子节点，天然满足堆性质。从最后一个非叶子节点（索引 (n/2) – 1）开始，保证处理每个节点时其子树已经是合法的堆。

#mermaid-svg-7VIXCfPvjhITrBZq{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-7VIXCfPvjhITrBZq .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-7VIXCfPvjhITrBZq .error-icon{fill:#552222;}#mermaid-svg-7VIXCfPvjhITrBZq .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-7VIXCfPvjhITrBZq .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-7VIXCfPvjhITrBZq .marker{fill:#333333;stroke:#333333;}#mermaid-svg-7VIXCfPvjhITrBZq .marker.cross{stroke:#333333;}#mermaid-svg-7VIXCfPvjhITrBZq svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-7VIXCfPvjhITrBZq p{margin:0;}#mermaid-svg-7VIXCfPvjhITrBZq .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-7VIXCfPvjhITrBZq .cluster-label text{fill:#333;}#mermaid-svg-7VIXCfPvjhITrBZq .cluster-label span{color:#333;}#mermaid-svg-7VIXCfPvjhITrBZq .cluster-label span p{background-color:transparent;}#mermaid-svg-7VIXCfPvjhITrBZq .label text,#mermaid-svg-7VIXCfPvjhITrBZq span{fill:#333;color:#333;}#mermaid-svg-7VIXCfPvjhITrBZq .node rect,#mermaid-svg-7VIXCfPvjhITrBZq .node circle,#mermaid-svg-7VIXCfPvjhITrBZq .node ellipse,#mermaid-svg-7VIXCfPvjhITrBZq .node polygon,#mermaid-svg-7VIXCfPvjhITrBZq .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-7VIXCfPvjhITrBZq .rough-node .label text,#mermaid-svg-7VIXCfPvjhITrBZq .node .label text,#mermaid-svg-7VIXCfPvjhITrBZq .image-shape .label,#mermaid-svg-7VIXCfPvjhITrBZq .icon-shape .label{text-anchor:middle;}#mermaid-svg-7VIXCfPvjhITrBZq .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-7VIXCfPvjhITrBZq .rough-node .label,#mermaid-svg-7VIXCfPvjhITrBZq .node .label,#mermaid-svg-7VIXCfPvjhITrBZq .image-shape .label,#mermaid-svg-7VIXCfPvjhITrBZq .icon-shape .label{text-align:center;}#mermaid-svg-7VIXCfPvjhITrBZq .node.clickable{cursor:pointer;}#mermaid-svg-7VIXCfPvjhITrBZq .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-7VIXCfPvjhITrBZq .arrowheadPath{fill:#333333;}#mermaid-svg-7VIXCfPvjhITrBZq .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-7VIXCfPvjhITrBZq .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-7VIXCfPvjhITrBZq .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7VIXCfPvjhITrBZq .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-7VIXCfPvjhITrBZq .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7VIXCfPvjhITrBZq .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-7VIXCfPvjhITrBZq .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-7VIXCfPvjhITrBZq .cluster text{fill:#333;}#mermaid-svg-7VIXCfPvjhITrBZq .cluster span{color:#333;}#mermaid-svg-7VIXCfPvjhITrBZq div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-7VIXCfPvjhITrBZq .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-7VIXCfPvjhITrBZq rect.text{fill:none;stroke-width:0;}#mermaid-svg-7VIXCfPvjhITrBZq .icon-shape,#mermaid-svg-7VIXCfPvjhITrBZq .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7VIXCfPvjhITrBZq .icon-shape p,#mermaid-svg-7VIXCfPvjhITrBZq .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-7VIXCfPvjhITrBZq .icon-shape .label rect,#mermaid-svg-7VIXCfPvjhITrBZq .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7VIXCfPvjhITrBZq .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-7VIXCfPvjhITrBZq .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-7VIXCfPvjhITrBZq :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

建堆过程 arr=[4,10,3,5,1,2]

初始数组: [4,10,3,5,1,2]

从索引2(节点3)开始3的子节点是2(左),无(右)3>2, 不用调整

索引1(节点10)子节点5和1, 10>5且10>1, 不用调整

索引0(节点4)子节点10和3, 4<10, 交换→[10,4,3,5,1,2]

4继续下沉4的子节点5和1, 4<5, 交换→[10,5,3,4,1,2]

建堆完成: [10,5,3,4,1,2]

图7-3：建堆过程——从最后一个非叶子节点向前逐个sift down，时间复杂度O(n)

// 建大顶堆
private static void buildHeap(int[] arr) {
int n = arr.length;
// 从最后一个非叶子节点开始
for (int i = n / 2 – 1; i >= 0; i—) {
siftDown(arr, i, n);
}
}

建堆的时间复杂度是 O(n)，不是 O(n log n)。

直觉上可能觉得：n/2 个节点每个 sift down 最多 log n 层，应该是 O(n log n)。但实际更紧的界是 O(n)，因为大部分节点在底层，下沉深度很小。

精确计算：第k层有 2^k 个节点，每个最多下沉 (h-k) 层（h为树高），总工作量为：

∑

k

=

0

h

2

k

⋅

(

h

−

k

)

=

∑

j

=

0

h

j

⋅

2

h

−

j

=

O

(

2

h

)

=

O

(

n

)

\\sum_{k=0}^{h} 2^k \\cdot (h-k) = \\sum_{j=0}^{h} j \\cdot 2^{h-j} = O(2^h) = O(n)

k=0∑h​2k⋅(h−k)=j=0∑h​j⋅2h−j=O(2h)=O(n)

这是一个收敛的级数，结果为 O(n)。

7.4 堆排序完整过程

建堆后，堆顶（arr[0]）就是最大值。排序过程：把最大值交换到末尾，缩小堆范围，再 sift down 调整。

#mermaid-svg-mPcUfXqKoBlKONVR{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-mPcUfXqKoBlKONVR .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-mPcUfXqKoBlKONVR .error-icon{fill:#552222;}#mermaid-svg-mPcUfXqKoBlKONVR .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-mPcUfXqKoBlKONVR .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-mPcUfXqKoBlKONVR .marker{fill:#333333;stroke:#333333;}#mermaid-svg-mPcUfXqKoBlKONVR .marker.cross{stroke:#333333;}#mermaid-svg-mPcUfXqKoBlKONVR svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-mPcUfXqKoBlKONVR p{margin:0;}#mermaid-svg-mPcUfXqKoBlKONVR .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-mPcUfXqKoBlKONVR .cluster-label text{fill:#333;}#mermaid-svg-mPcUfXqKoBlKONVR .cluster-label span{color:#333;}#mermaid-svg-mPcUfXqKoBlKONVR .cluster-label span p{background-color:transparent;}#mermaid-svg-mPcUfXqKoBlKONVR .label text,#mermaid-svg-mPcUfXqKoBlKONVR span{fill:#333;color:#333;}#mermaid-svg-mPcUfXqKoBlKONVR .node rect,#mermaid-svg-mPcUfXqKoBlKONVR .node circle,#mermaid-svg-mPcUfXqKoBlKONVR .node ellipse,#mermaid-svg-mPcUfXqKoBlKONVR .node polygon,#mermaid-svg-mPcUfXqKoBlKONVR .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-mPcUfXqKoBlKONVR .rough-node .label text,#mermaid-svg-mPcUfXqKoBlKONVR .node .label text,#mermaid-svg-mPcUfXqKoBlKONVR .image-shape .label,#mermaid-svg-mPcUfXqKoBlKONVR .icon-shape .label{text-anchor:middle;}#mermaid-svg-mPcUfXqKoBlKONVR .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-mPcUfXqKoBlKONVR .rough-node .label,#mermaid-svg-mPcUfXqKoBlKONVR .node .label,#mermaid-svg-mPcUfXqKoBlKONVR .image-shape .label,#mermaid-svg-mPcUfXqKoBlKONVR .icon-shape .label{text-align:center;}#mermaid-svg-mPcUfXqKoBlKONVR .node.clickable{cursor:pointer;}#mermaid-svg-mPcUfXqKoBlKONVR .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-mPcUfXqKoBlKONVR .arrowheadPath{fill:#333333;}#mermaid-svg-mPcUfXqKoBlKONVR .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-mPcUfXqKoBlKONVR .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-mPcUfXqKoBlKONVR .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mPcUfXqKoBlKONVR .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-mPcUfXqKoBlKONVR .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mPcUfXqKoBlKONVR .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-mPcUfXqKoBlKONVR .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-mPcUfXqKoBlKONVR .cluster text{fill:#333;}#mermaid-svg-mPcUfXqKoBlKONVR .cluster span{color:#333;}#mermaid-svg-mPcUfXqKoBlKONVR div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-mPcUfXqKoBlKONVR .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-mPcUfXqKoBlKONVR rect.text{fill:none;stroke-width:0;}#mermaid-svg-mPcUfXqKoBlKONVR .icon-shape,#mermaid-svg-mPcUfXqKoBlKONVR .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mPcUfXqKoBlKONVR .icon-shape p,#mermaid-svg-mPcUfXqKoBlKONVR .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-mPcUfXqKoBlKONVR .icon-shape .label rect,#mermaid-svg-mPcUfXqKoBlKONVR .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mPcUfXqKoBlKONVR .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-mPcUfXqKoBlKONVR .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-mPcUfXqKoBlKONVR :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

堆排序过程（建堆后 [10,5,3,4,1,2]）

大顶堆: [10,5,3,4,1,2]

交换arr[0]↔arr[5] → [2,5,3,4,1|10]siftDown(0,5) → [5,4,3,2,1|10]

交换arr[0]↔arr[4] → [1,4,3,2|5,10]siftDown(0,4) → [4,2,3,1|5,10]

交换arr[0]↔arr[3] → [1,2,3|4,5,10]siftDown(0,3) → [3,2,1|4,5,10]

交换arr[0]↔arr[2] → [1,2|3,4,5,10]siftDown(0,2) → [2,1|3,4,5,10]

交换arr[0]↔arr[1] → [1|2,3,4,5,10]siftDown(0,1) → [1|2,3,4,5,10]

完成: [1,2,3,4,5,10]

图7-4：堆排序——反复取堆顶最大值放到末尾（橙色），缩小堆并sift down调整。竖线左侧为堆，右侧为已排序部分

public static void heapSort(int[] arr) {
int n = arr.length;
// 1. 建大顶堆
buildHeap(arr);
// 2. 反复取堆顶最大值放到末尾
for (int i = n – 1; i > 0; i—) {
swap(arr, 0, i); // 最大值放到末尾
siftDown(arr, 0, i); // 调整堆，范围缩小到[0, i)
}
}

7.5 复杂度分析

时间复杂度：

堆排序的最好、平均、最坏都是 O(n log n)，没有退化问题。这是它相对于快排的优势。

空间复杂度：O(1)，原地排序，不需要额外空间。

7.6 稳定性分析

堆排序是不稳定的。

不稳定的原因在建堆和排序过程中的跨越式交换。考虑数组 [5a, 5b, 3]：

建大顶堆：
索引0(5a)的子节点是5b和3，5a≥5b且5a≥3，无需调整
建堆后: [5a, 5b, 3]

排序第1步：
交换arr[0]↔arr[2] → [3, 5b, 5a] ← 5a跑到了5b后面

堆排序中的交换（堆顶与末尾交换、sift down 中的父子交换）都不是相邻交换，无法保证相等元素的相对顺序。

7.7 堆排序 vs 快排

堆排序最坏O(n log n)看似比快排更优，但实际工程中快排通常更快。关键的差异在缓存：

堆排序中，sift down 需要访问 i、2i+1、2i+2 这三个位置，索引跨度大，缓存命中率低。当数组较大时，几乎每次访问都是缓存未命中。快排的 partition 是顺序扫描，CPU 预取机制能提前加载数据，缓存命中率高。

这就是为什么 C++ STL 的 sort 用 IntroSort（快排为主、退化时切堆排），而不是直接用堆排——快排在正常情况下更快，只在快排退化时才用堆排兜底。

7.8 堆排序的核心应用：Top-K 问题

堆排序在工程中最重要的应用不是全量排序，而是 Top-K 问题：从n个元素中找最大/最小的k个。

#mermaid-svg-ST1U8FMJAC2rIlL2{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-ST1U8FMJAC2rIlL2 .error-icon{fill:#552222;}#mermaid-svg-ST1U8FMJAC2rIlL2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ST1U8FMJAC2rIlL2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .marker.cross{stroke:#333333;}#mermaid-svg-ST1U8FMJAC2rIlL2 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ST1U8FMJAC2rIlL2 p{margin:0;}#mermaid-svg-ST1U8FMJAC2rIlL2 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster-label text{fill:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster-label span{color:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster-label span p{background-color:transparent;}#mermaid-svg-ST1U8FMJAC2rIlL2 .label text,#mermaid-svg-ST1U8FMJAC2rIlL2 span{fill:#333;color:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .node rect,#mermaid-svg-ST1U8FMJAC2rIlL2 .node circle,#mermaid-svg-ST1U8FMJAC2rIlL2 .node ellipse,#mermaid-svg-ST1U8FMJAC2rIlL2 .node polygon,#mermaid-svg-ST1U8FMJAC2rIlL2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .rough-node .label text,#mermaid-svg-ST1U8FMJAC2rIlL2 .node .label text,#mermaid-svg-ST1U8FMJAC2rIlL2 .image-shape .label,#mermaid-svg-ST1U8FMJAC2rIlL2 .icon-shape .label{text-anchor:middle;}#mermaid-svg-ST1U8FMJAC2rIlL2 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .rough-node .label,#mermaid-svg-ST1U8FMJAC2rIlL2 .node .label,#mermaid-svg-ST1U8FMJAC2rIlL2 .image-shape .label,#mermaid-svg-ST1U8FMJAC2rIlL2 .icon-shape .label{text-align:center;}#mermaid-svg-ST1U8FMJAC2rIlL2 .node.clickable{cursor:pointer;}#mermaid-svg-ST1U8FMJAC2rIlL2 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .arrowheadPath{fill:#333333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-ST1U8FMJAC2rIlL2 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-ST1U8FMJAC2rIlL2 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-ST1U8FMJAC2rIlL2 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster text{fill:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 .cluster span{color:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ST1U8FMJAC2rIlL2 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-ST1U8FMJAC2rIlL2 rect.text{fill:none;stroke-width:0;}#mermaid-svg-ST1U8FMJAC2rIlL2 .icon-shape,#mermaid-svg-ST1U8FMJAC2rIlL2 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-ST1U8FMJAC2rIlL2 .icon-shape p,#mermaid-svg-ST1U8FMJAC2rIlL2 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-ST1U8FMJAC2rIlL2 .icon-shape .label rect,#mermaid-svg-ST1U8FMJAC2rIlL2 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-ST1U8FMJAC2rIlL2 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-ST1U8FMJAC2rIlL2 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-ST1U8FMJAC2rIlL2 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

Top-K问题（找最大的k=3个元素）

是

否

10亿条数据

维护大小为3的小顶堆

遍历每个元素:

元素 > 堆顶?

替换堆顶, siftDown调整O(log k)

跳过

遍历完成堆中就是最大的3个

图7-5：Top-K问题——维护大小为k的堆，O(n log k)解决。比全量排序O(n log n)快得多

// 找第k大的元素（LeetCode 215）
public static int findKthLargest(int[] nums, int k) {
// 用小顶堆维护当前最大的k个元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // 堆顶（最小）出堆
}
}
return minHeap.peek(); // 堆顶就是第k大
}

为什么用小顶堆找最大的k个？因为小顶堆的堆顶是当前k个元素中的最小值。新元素如果比堆顶大，说明它应该进堆；如果比堆顶小，说明它不可能在前k大中。每次操作 O(log k)，总复杂度 O(n log k)。

对比全量排序 O(n log n)，当 k 远小于 n 时，Top-K 方法快得多。而且只需要 O(k) 额外空间，适合流式数据（不需要一次性加载所有数据）。

第8章 非比较排序：计数、基数与桶排序

前面7种排序算法都是比较排序，最坏情况下至少 O(n log n)。本章介绍三种非比较排序，它们突破了这个下界，但各有适用条件。

8.1 计数排序（Counting Sort）

8.1.1 核心思想

计数排序不是比较元素大小，而是统计每个值出现的次数，然后根据统计结果直接把元素放到正确位置。

适用条件：元素是非负整数，且取值范围 k 不太大（通常 k = O(n)）。例如对100万个年龄数据（0-150）排序，k=151 远小于 n=1000000，非常适合计数排序。

8.1.2 执行过程图解

以 [4, 2, 2, 8, 3, 3, 1] 为例（取值范围0-8）：

#mermaid-svg-IfvfT3BUugzDIrCe{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-IfvfT3BUugzDIrCe .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-IfvfT3BUugzDIrCe .error-icon{fill:#552222;}#mermaid-svg-IfvfT3BUugzDIrCe .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-IfvfT3BUugzDIrCe .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-IfvfT3BUugzDIrCe .marker{fill:#333333;stroke:#333333;}#mermaid-svg-IfvfT3BUugzDIrCe .marker.cross{stroke:#333333;}#mermaid-svg-IfvfT3BUugzDIrCe svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-IfvfT3BUugzDIrCe p{margin:0;}#mermaid-svg-IfvfT3BUugzDIrCe .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-IfvfT3BUugzDIrCe .cluster-label text{fill:#333;}#mermaid-svg-IfvfT3BUugzDIrCe .cluster-label span{color:#333;}#mermaid-svg-IfvfT3BUugzDIrCe .cluster-label span p{background-color:transparent;}#mermaid-svg-IfvfT3BUugzDIrCe .label text,#mermaid-svg-IfvfT3BUugzDIrCe span{fill:#333;color:#333;}#mermaid-svg-IfvfT3BUugzDIrCe .node rect,#mermaid-svg-IfvfT3BUugzDIrCe .node circle,#mermaid-svg-IfvfT3BUugzDIrCe .node ellipse,#mermaid-svg-IfvfT3BUugzDIrCe .node polygon,#mermaid-svg-IfvfT3BUugzDIrCe .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-IfvfT3BUugzDIrCe .rough-node .label text,#mermaid-svg-IfvfT3BUugzDIrCe .node .label text,#mermaid-svg-IfvfT3BUugzDIrCe .image-shape .label,#mermaid-svg-IfvfT3BUugzDIrCe .icon-shape .label{text-anchor:middle;}#mermaid-svg-IfvfT3BUugzDIrCe .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-IfvfT3BUugzDIrCe .rough-node .label,#mermaid-svg-IfvfT3BUugzDIrCe .node .label,#mermaid-svg-IfvfT3BUugzDIrCe .image-shape .label,#mermaid-svg-IfvfT3BUugzDIrCe .icon-shape .label{text-align:center;}#mermaid-svg-IfvfT3BUugzDIrCe .node.clickable{cursor:pointer;}#mermaid-svg-IfvfT3BUugzDIrCe .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-IfvfT3BUugzDIrCe .arrowheadPath{fill:#333333;}#mermaid-svg-IfvfT3BUugzDIrCe .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-IfvfT3BUugzDIrCe .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-IfvfT3BUugzDIrCe .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-IfvfT3BUugzDIrCe .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-IfvfT3BUugzDIrCe .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-IfvfT3BUugzDIrCe .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-IfvfT3BUugzDIrCe .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-IfvfT3BUugzDIrCe .cluster text{fill:#333;}#mermaid-svg-IfvfT3BUugzDIrCe .cluster span{color:#333;}#mermaid-svg-IfvfT3BUugzDIrCe div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-IfvfT3BUugzDIrCe .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-IfvfT3BUugzDIrCe rect.text{fill:none;stroke-width:0;}#mermaid-svg-IfvfT3BUugzDIrCe .icon-shape,#mermaid-svg-IfvfT3BUugzDIrCe .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-IfvfT3BUugzDIrCe .icon-shape p,#mermaid-svg-IfvfT3BUugzDIrCe .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-IfvfT3BUugzDIrCe .icon-shape .label rect,#mermaid-svg-IfvfT3BUugzDIrCe .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-IfvfT3BUugzDIrCe .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-IfvfT3BUugzDIrCe .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-IfvfT3BUugzDIrCe :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

计数排序过程

输入: [4, 2, 2, 8, 3, 3, 1]

第1步: 统计频次count[0]=0, count[1]=1, count[2]=2count[3]=2, count[4]=1, count[5]=0count[6]=0, count[7]=0, count[8]=1

第2步: 前缀和（计算位置）pos[0]=0, pos[1]=1, pos[2]=3pos[3]=5, pos[4]=6, pos[5]=6pos[6]=6, pos[7]=6, pos[8]=7

第3步: 逆序遍历填入输出数组1→索引0, 3→索引4, 3→索引38→索引6, 2→索引2, 2→索引1, 4→索引5

输出: [1, 2, 2, 3, 3, 4, 8]

图8-1：计数排序——统计频次→前缀和定位→逆序填入保证稳定性

为什么要前缀和？前缀和后 count[v] 表示 ≤v 的元素总数，即值v应放置的最后一个位置+1。例如 count[3] = 5 表示有5个元素 ≤3（一个1、两个2、两个3），两个3通过 –count[3] 分别放到索引4和3。

为什么要逆序遍历：逆序遍历输入数组并通过 pos[v]– 来放置元素，保证相同值的元素保持原来的先后顺序——后面的先放（放到后面），前面的后放（放到前面），从而实现稳定排序。

8.1.3 代码实现

public static void countingSort(int[] arr) {
if (arr.length <= 1) return;

// 1. 找最大值确定范围
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}

// 2. 统计频次
int[] count = new int[max + 1];
for (int num : arr) {
count[num]++;
}

// 3. 前缀和（计算每个值的起始位置）
for (int i = 1; i <= max; i++) {
count[i] += count[i – 1];
}
// 此时count[v]表示值v的最后一个位置+1

// 4. 逆序遍历，填入输出数组（保证稳定性）
int[] output = new int[arr.length];
for (int i = arr.length – 1; i >= 0; i—) {
int v = arr[i];
output[—count[v]] = v; // 先减1再放
}

// 5. 拷回原数组
System.arraycopy(output, 0, arr, 0, arr.length);
}

8.1.4 复杂度分析

• 时间：O(n + k)，n为元素个数，k为取值范围。找最大值O(n)，统计O(n)，前缀和O(k)，填充O(n)
• 空间：O(n + k)，count数组O(k)，output数组O(n)
• 稳定性：稳定。逆序遍历 + 前缀和递减保证相等元素保持原序

什么时候计数排序比快排快：当 k = O(n) 时，O(n+k) = O(n)，远快于 O(n log n)。当 k >> n 时（如n=100，k=10^9），count数组太大，不适用。

8.2 基数排序（Radix Sort）

8.2.1 核心思想

基数排序对整数的每一位分别排序，从最低位到最高位（LSD，Least Significant Digit）或从最高位到最低位（MSD）。每一次"按某位排序"使用计数排序（因为数字0-9只有10个取值）。

为什么从最低位开始（LSD）有效？因为高位的排序是最终的排序依据，低位排序不能打乱高位已排好的顺序。稳定排序是关键——如果某位排序不稳定，高位的排序结果就会被低位打乱。

8.2.2 执行过程图解

以 [329, 457, 657, 839, 436, 720, 355] 为例：

#mermaid-svg-hgsrXKJU9DvzCU56{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-hgsrXKJU9DvzCU56 .error-icon{fill:#552222;}#mermaid-svg-hgsrXKJU9DvzCU56 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-hgsrXKJU9DvzCU56 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-hgsrXKJU9DvzCU56 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-hgsrXKJU9DvzCU56 .marker.cross{stroke:#333333;}#mermaid-svg-hgsrXKJU9DvzCU56 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-hgsrXKJU9DvzCU56 p{margin:0;}#mermaid-svg-hgsrXKJU9DvzCU56 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster-label text{fill:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster-label span{color:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster-label span p{background-color:transparent;}#mermaid-svg-hgsrXKJU9DvzCU56 .label text,#mermaid-svg-hgsrXKJU9DvzCU56 span{fill:#333;color:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 .node rect,#mermaid-svg-hgsrXKJU9DvzCU56 .node circle,#mermaid-svg-hgsrXKJU9DvzCU56 .node ellipse,#mermaid-svg-hgsrXKJU9DvzCU56 .node polygon,#mermaid-svg-hgsrXKJU9DvzCU56 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-hgsrXKJU9DvzCU56 .rough-node .label text,#mermaid-svg-hgsrXKJU9DvzCU56 .node .label text,#mermaid-svg-hgsrXKJU9DvzCU56 .image-shape .label,#mermaid-svg-hgsrXKJU9DvzCU56 .icon-shape .label{text-anchor:middle;}#mermaid-svg-hgsrXKJU9DvzCU56 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-hgsrXKJU9DvzCU56 .rough-node .label,#mermaid-svg-hgsrXKJU9DvzCU56 .node .label,#mermaid-svg-hgsrXKJU9DvzCU56 .image-shape .label,#mermaid-svg-hgsrXKJU9DvzCU56 .icon-shape .label{text-align:center;}#mermaid-svg-hgsrXKJU9DvzCU56 .node.clickable{cursor:pointer;}#mermaid-svg-hgsrXKJU9DvzCU56 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-hgsrXKJU9DvzCU56 .arrowheadPath{fill:#333333;}#mermaid-svg-hgsrXKJU9DvzCU56 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-hgsrXKJU9DvzCU56 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-hgsrXKJU9DvzCU56 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-hgsrXKJU9DvzCU56 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-hgsrXKJU9DvzCU56 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-hgsrXKJU9DvzCU56 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster text{fill:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 .cluster span{color:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-hgsrXKJU9DvzCU56 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-hgsrXKJU9DvzCU56 rect.text{fill:none;stroke-width:0;}#mermaid-svg-hgsrXKJU9DvzCU56 .icon-shape,#mermaid-svg-hgsrXKJU9DvzCU56 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-hgsrXKJU9DvzCU56 .icon-shape p,#mermaid-svg-hgsrXKJU9DvzCU56 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-hgsrXKJU9DvzCU56 .icon-shape .label rect,#mermaid-svg-hgsrXKJU9DvzCU56 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-hgsrXKJU9DvzCU56 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-hgsrXKJU9DvzCU56 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-hgsrXKJU9DvzCU56 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

LSD基数排序（从个位到百位）

原始: [329, 457, 657, 839, 436, 720, 355]

按个位排序:720(0) 355(5) 436(6) 457(7) 657(7) 329(9) 839(9)→ [720, 355, 436, 457, 657, 329, 839]

按十位排序:720(2) 329(2) 436(3) 839(3) 355(5) 457(5) 657(5)→ [720, 329, 436, 839, 355, 457, 657]

按百位排序:329(3) 355(3) 436(4) 457(4) 657(6) 720(7) 839(8)→ [329, 355, 436, 457, 657, 720, 839]

完成: [329, 355, 436, 457, 657, 720, 839]

图8-2：LSD基数排序——从个位到百位，每轮用计数排序按当前位排序。注意457和657个位都为7，第1轮后457在前657在后，后续轮次必须保持这个顺序（稳定性）

验证稳定性：457和657，个位都是7。第1轮按个位排序后，457（原索引1）在657（原索引2）前面。后续轮次中十位5=5、百位4<6，排序正确。如果某轮排序不稳定，457和657可能被反转为657在前。

8.2.3 代码实现

public static void radixSort(int[] arr) {
if (arr.length <= 1) return;

// 找最大值确定位数
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}

// 从个位到最高位，每位用计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}

// 按第exp位进行计数排序
private static void countingSortByDigit(int[] arr, int exp) {
int n = arr.length;
int[] output = new int[n];
int[] count = new int[10]; // 0-9

// 统计当前位的频次
for (int num : arr) {
int digit = (num / exp) % 10;
count[digit]++;
}

// 前缀和
for (int i = 1; i < 10; i++) {
count[i] += count[i – 1];
}

// 逆序填充（保证稳定性）
for (int i = n – 1; i >= 0; i—) {
int digit = (arr[i] / exp) % 10;
output[—count[digit]] = arr[i];
}

System.arraycopy(output, 0, arr, 0, n);
}

8.2.4 复杂度分析

• 时间：O(d · (n + k))，d为最大位数，k为基数（此处k=10）。对32位整数，d最多10位
• 空间：O(n + k)
• 稳定性：稳定（每轮计数排序都是稳定的）

当 d 为常数时（如固定长度整数），基数排序是 O(n) 的。但实际中 d · (n + k) 的常数因子可能使它不如快排快，特别是当数据可以用比较排序高效处理时。

基数排序还可以用于字符串排序——按字符从后向前（或从前向后）逐位排序。但字符串长度不固定，处理较复杂。

8.3 桶排序（Bucket Sort）

8.3.1 核心思想

桶排序把数据按值域分到若干个"桶"中，每个桶内部单独排序，然后依次拼接。当数据均匀分布时，每个桶内数据量很少（平均n/k个），桶内排序很快，总复杂度接近 O(n)。

#mermaid-svg-08eGkPhR88lVqKLH{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-08eGkPhR88lVqKLH .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-08eGkPhR88lVqKLH .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-08eGkPhR88lVqKLH .error-icon{fill:#552222;}#mermaid-svg-08eGkPhR88lVqKLH .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-08eGkPhR88lVqKLH .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-08eGkPhR88lVqKLH .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-08eGkPhR88lVqKLH .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-08eGkPhR88lVqKLH .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-08eGkPhR88lVqKLH .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-08eGkPhR88lVqKLH .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-08eGkPhR88lVqKLH .marker{fill:#333333;stroke:#333333;}#mermaid-svg-08eGkPhR88lVqKLH .marker.cross{stroke:#333333;}#mermaid-svg-08eGkPhR88lVqKLH svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-08eGkPhR88lVqKLH p{margin:0;}#mermaid-svg-08eGkPhR88lVqKLH .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-08eGkPhR88lVqKLH .cluster-label text{fill:#333;}#mermaid-svg-08eGkPhR88lVqKLH .cluster-label span{color:#333;}#mermaid-svg-08eGkPhR88lVqKLH .cluster-label span p{background-color:transparent;}#mermaid-svg-08eGkPhR88lVqKLH .label text,#mermaid-svg-08eGkPhR88lVqKLH span{fill:#333;color:#333;}#mermaid-svg-08eGkPhR88lVqKLH .node rect,#mermaid-svg-08eGkPhR88lVqKLH .node circle,#mermaid-svg-08eGkPhR88lVqKLH .node ellipse,#mermaid-svg-08eGkPhR88lVqKLH .node polygon,#mermaid-svg-08eGkPhR88lVqKLH .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-08eGkPhR88lVqKLH .rough-node .label text,#mermaid-svg-08eGkPhR88lVqKLH .node .label text,#mermaid-svg-08eGkPhR88lVqKLH .image-shape .label,#mermaid-svg-08eGkPhR88lVqKLH .icon-shape .label{text-anchor:middle;}#mermaid-svg-08eGkPhR88lVqKLH .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-08eGkPhR88lVqKLH .rough-node .label,#mermaid-svg-08eGkPhR88lVqKLH .node .label,#mermaid-svg-08eGkPhR88lVqKLH .image-shape .label,#mermaid-svg-08eGkPhR88lVqKLH .icon-shape .label{text-align:center;}#mermaid-svg-08eGkPhR88lVqKLH .node.clickable{cursor:pointer;}#mermaid-svg-08eGkPhR88lVqKLH .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-08eGkPhR88lVqKLH .arrowheadPath{fill:#333333;}#mermaid-svg-08eGkPhR88lVqKLH .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-08eGkPhR88lVqKLH .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-08eGkPhR88lVqKLH .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-08eGkPhR88lVqKLH .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-08eGkPhR88lVqKLH .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-08eGkPhR88lVqKLH .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-08eGkPhR88lVqKLH .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-08eGkPhR88lVqKLH .cluster text{fill:#333;}#mermaid-svg-08eGkPhR88lVqKLH .cluster span{color:#333;}#mermaid-svg-08eGkPhR88lVqKLH div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-08eGkPhR88lVqKLH .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-08eGkPhR88lVqKLH rect.text{fill:none;stroke-width:0;}#mermaid-svg-08eGkPhR88lVqKLH .icon-shape,#mermaid-svg-08eGkPhR88lVqKLH .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-08eGkPhR88lVqKLH .icon-shape p,#mermaid-svg-08eGkPhR88lVqKLH .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-08eGkPhR88lVqKLH .icon-shape .label rect,#mermaid-svg-08eGkPhR88lVqKLH .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-08eGkPhR88lVqKLH .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-08eGkPhR88lVqKLH .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-08eGkPhR88lVqKLH :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

桶排序过程 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

输入: 10个[0,1)的浮点数

分到5个桶（区间0.2）

桶0[0,0.2): [0.17, 0.12] → 排序 → [0.12, 0.17]

桶1[0.2,0.4): [0.26, 0.21, 0.23] → 排序 → [0.21, 0.23, 0.26]

桶2[0.4,0.6): [0.39] → 已排序

桶3[0.6,0.8): [0.78, 0.72, 0.68] → 排序 → [0.68, 0.72, 0.78]

桶4[0.8,1.0): [0.94] → 已排序

拼接: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

图8-3：桶排序——按值域分桶，桶内排序后拼接。数据均匀分布时每个桶约n/k个元素

8.3.2 代码实现

public static void bucketSort(double[] arr) {
int n = arr.length;
if (n <= 1) return;

// 1. 创建桶
int bucketCount = n; // 桶数量等于元素数量
List<List<Double>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}

// 2. 分配元素到桶中
for (double num : arr) {
int idx = (int) (num * bucketCount); // 映射到桶索引
if (idx >= bucketCount) idx = bucketCount – 1; // 处理上界
buckets.get(idx).add(num);
}

// 3. 每个桶内部排序（用插入排序或Collections.sort）
for (List<Double> bucket : buckets) {
Collections.sort(bucket); // 实际可用插入排序优化小桶
}

// 4. 依次拼接
int idx = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) {
arr[idx++] = num;
}
}
}

8.3.3 复杂度分析

• 最好/平均：O(n + k)，数据均匀分布时每个桶O(n/k)个元素，k个桶共O(n)，桶内排序O(n/k · log(n/k))
• 最坏：O(n²)，所有数据集中到一个桶，退化为桶内排序的复杂度
• 空间：O(n + k)
• 稳定性：取决于桶内排序算法是否稳定。用稳定的排序（如插入排序、归并排序）则桶排序稳定

桶排序的性能高度依赖数据分布。如果数据均匀分布，是最快的排序之一。如果分布不均（如数据集中在某一区间），性能退化。

8.4 非比较排序对比

第9章 工程实践：TimSort、IntroSort与库实现选型

前面8章讲解的是"教科书"排序算法。实际工程中，主流语言的标准库不会只用一种排序算法，而是采用混合策略——根据数据特征动态切换最优算法。本章揭秘三大主流语言的排序库实现。

9.1 TimSort：Python & Java 的选择

TimSort 由 Tim Peters 于2002年发明，应用于Python的sorted()和list.sort()，以及Java 7+的Arrays.sort(Object[])（对象数组）。它是归并排序 + 插入排序的混合体。

9.1.1 核心思想

TimSort 的关键洞察是：现实数据往往部分有序。它通过检测数组中的"run"（连续递增或递减的子序列）来利用已有的有序性，减少排序工作量。

#mermaid-svg-E11UvL2HctxdSlBJ{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-E11UvL2HctxdSlBJ .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-E11UvL2HctxdSlBJ .error-icon{fill:#552222;}#mermaid-svg-E11UvL2HctxdSlBJ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-E11UvL2HctxdSlBJ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-E11UvL2HctxdSlBJ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-E11UvL2HctxdSlBJ .marker.cross{stroke:#333333;}#mermaid-svg-E11UvL2HctxdSlBJ svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-E11UvL2HctxdSlBJ p{margin:0;}#mermaid-svg-E11UvL2HctxdSlBJ .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-E11UvL2HctxdSlBJ .cluster-label text{fill:#333;}#mermaid-svg-E11UvL2HctxdSlBJ .cluster-label span{color:#333;}#mermaid-svg-E11UvL2HctxdSlBJ .cluster-label span p{background-color:transparent;}#mermaid-svg-E11UvL2HctxdSlBJ .label text,#mermaid-svg-E11UvL2HctxdSlBJ span{fill:#333;color:#333;}#mermaid-svg-E11UvL2HctxdSlBJ .node rect,#mermaid-svg-E11UvL2HctxdSlBJ .node circle,#mermaid-svg-E11UvL2HctxdSlBJ .node ellipse,#mermaid-svg-E11UvL2HctxdSlBJ .node polygon,#mermaid-svg-E11UvL2HctxdSlBJ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-E11UvL2HctxdSlBJ .rough-node .label text,#mermaid-svg-E11UvL2HctxdSlBJ .node .label text,#mermaid-svg-E11UvL2HctxdSlBJ .image-shape .label,#mermaid-svg-E11UvL2HctxdSlBJ .icon-shape .label{text-anchor:middle;}#mermaid-svg-E11UvL2HctxdSlBJ .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-E11UvL2HctxdSlBJ .rough-node .label,#mermaid-svg-E11UvL2HctxdSlBJ .node .label,#mermaid-svg-E11UvL2HctxdSlBJ .image-shape .label,#mermaid-svg-E11UvL2HctxdSlBJ .icon-shape .label{text-align:center;}#mermaid-svg-E11UvL2HctxdSlBJ .node.clickable{cursor:pointer;}#mermaid-svg-E11UvL2HctxdSlBJ .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-E11UvL2HctxdSlBJ .arrowheadPath{fill:#333333;}#mermaid-svg-E11UvL2HctxdSlBJ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-E11UvL2HctxdSlBJ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-E11UvL2HctxdSlBJ .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-E11UvL2HctxdSlBJ .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-E11UvL2HctxdSlBJ .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-E11UvL2HctxdSlBJ .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-E11UvL2HctxdSlBJ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-E11UvL2HctxdSlBJ .cluster text{fill:#333;}#mermaid-svg-E11UvL2HctxdSlBJ .cluster span{color:#333;}#mermaid-svg-E11UvL2HctxdSlBJ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-E11UvL2HctxdSlBJ .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-E11UvL2HctxdSlBJ rect.text{fill:none;stroke-width:0;}#mermaid-svg-E11UvL2HctxdSlBJ .icon-shape,#mermaid-svg-E11UvL2HctxdSlBJ .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-E11UvL2HctxdSlBJ .icon-shape p,#mermaid-svg-E11UvL2HctxdSlBJ .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-E11UvL2HctxdSlBJ .icon-shape .label rect,#mermaid-svg-E11UvL2HctxdSlBJ .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-E11UvL2HctxdSlBJ .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-E11UvL2HctxdSlBJ .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-E11UvL2HctxdSlBJ :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

TimSort 工作流程

输入数组

1. 识别runs连续递增/递减的子序列

2. 反转递减runs使其递增

3. 用栈合并runs维持栈顶三个run的不变式

4. 小run（<32）用插入排序扩展

5. 最终合并所有runs

有序输出

图9-1：TimSort工作流程——识别有序段(runs)、小段用插入排序、大段用归并合并

9.1.2 关键优化

优化1：Run识别与利用

TimSort扫描数组，找到连续递增或递减的子序列（称为run）。递减的run被反转成递增。一个长度为n的完全有序数组就是一个长度为n的run——直接跳过排序，因此TimSort对已有序数据是O(n)。

优化2：最小run长度（minRun）

TimSort设定一个最小run长度（通常32-64）。如果找到的run短于minRun，用插入排序扩展它。这利用了插入排序对小数组极快的特性。

优化3：合并栈与不变式

TimSort维护一个run栈，用类似归并排序的方式合并。但合并策略更精细——维持栈高三个run满足 len(top-2) > len(top-1) + len(top) 和 len(top-1) > len(top) 的不变式，保证合并的平衡性，避免退化。

优化4：Galloping Mode（飞奔模式）

当合并两个run时，如果一侧连续多次"胜出"（某个run的元素连续被选入结果），切换到galloping模式——用二分查找一次性找到一大批应该来自同一侧的元素，减少逐个比较的开销。

9.1.3 复杂度

TimSort是稳定排序，这是Python和Java选择它而非快排的主要原因——对象排序通常需要稳定性（如先按年龄排序再按姓名排序）。

9.2 IntroSort：C++ STL 的选择

IntroSort（内省排序）由 David Musser 于1997年提出，应用于C++ STL的std::sort。它是快速排序 + 堆排序 + 插入排序的三合一。

9.2.1 核心思想

IntroSort以快排为主，但有两个安全阀：

#mermaid-svg-BxL0yai2PPkwpwp4{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-BxL0yai2PPkwpwp4 .error-icon{fill:#552222;}#mermaid-svg-BxL0yai2PPkwpwp4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-BxL0yai2PPkwpwp4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-BxL0yai2PPkwpwp4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-BxL0yai2PPkwpwp4 .marker.cross{stroke:#333333;}#mermaid-svg-BxL0yai2PPkwpwp4 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-BxL0yai2PPkwpwp4 p{margin:0;}#mermaid-svg-BxL0yai2PPkwpwp4 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster-label text{fill:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster-label span{color:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster-label span p{background-color:transparent;}#mermaid-svg-BxL0yai2PPkwpwp4 .label text,#mermaid-svg-BxL0yai2PPkwpwp4 span{fill:#333;color:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 .node rect,#mermaid-svg-BxL0yai2PPkwpwp4 .node circle,#mermaid-svg-BxL0yai2PPkwpwp4 .node ellipse,#mermaid-svg-BxL0yai2PPkwpwp4 .node polygon,#mermaid-svg-BxL0yai2PPkwpwp4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-BxL0yai2PPkwpwp4 .rough-node .label text,#mermaid-svg-BxL0yai2PPkwpwp4 .node .label text,#mermaid-svg-BxL0yai2PPkwpwp4 .image-shape .label,#mermaid-svg-BxL0yai2PPkwpwp4 .icon-shape .label{text-anchor:middle;}#mermaid-svg-BxL0yai2PPkwpwp4 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-BxL0yai2PPkwpwp4 .rough-node .label,#mermaid-svg-BxL0yai2PPkwpwp4 .node .label,#mermaid-svg-BxL0yai2PPkwpwp4 .image-shape .label,#mermaid-svg-BxL0yai2PPkwpwp4 .icon-shape .label{text-align:center;}#mermaid-svg-BxL0yai2PPkwpwp4 .node.clickable{cursor:pointer;}#mermaid-svg-BxL0yai2PPkwpwp4 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-BxL0yai2PPkwpwp4 .arrowheadPath{fill:#333333;}#mermaid-svg-BxL0yai2PPkwpwp4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-BxL0yai2PPkwpwp4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-BxL0yai2PPkwpwp4 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-BxL0yai2PPkwpwp4 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-BxL0yai2PPkwpwp4 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-BxL0yai2PPkwpwp4 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster text{fill:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 .cluster span{color:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-BxL0yai2PPkwpwp4 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-BxL0yai2PPkwpwp4 rect.text{fill:none;stroke-width:0;}#mermaid-svg-BxL0yai2PPkwpwp4 .icon-shape,#mermaid-svg-BxL0yai2PPkwpwp4 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-BxL0yai2PPkwpwp4 .icon-shape p,#mermaid-svg-BxL0yai2PPkwpwp4 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-BxL0yai2PPkwpwp4 .icon-shape .label rect,#mermaid-svg-BxL0yai2PPkwpwp4 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-BxL0yai2PPkwpwp4 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-BxL0yai2PPkwpwp4 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-BxL0yai2PPkwpwp4 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

IntroSort 决策流程

是

否

是

否

输入 n

n < 16?

插入排序O(n²)但常数小

递归深度 > 2log₂n?

堆排序保证O(n log n)

快速排序三数取中pivot

分区后递归

完成

图9-2：IntroSort混合策略——正常用快排（蓝），深度超限切堆排（橙），小区间切插入排序（绿）

9.2.2 为什么这样设计

• 快排打底：大多数情况下快排最快（缓存友好、常数因子小），作为主算法
• 堆排兜底：快排最坏O(n²)，用递归深度检测何时快排要退化，及时切到堆排
• 插入排序收尾：小区域内快排的递归开销不值当，切换到插入排序更高效

IntroSort是不稳定排序——快排和堆排都不稳定。C++ STL另外提供了std::stable_sort（基于归并排序），需要稳定性时使用。

9.3 各语言标准库排序实现

表9-1：主流语言排序库实现——对象/稳定需求用TimSort/归并，基本类型用快排变体

为什么Java对基本类型和对象用不同排序：

9.4 工程选型决策树

#mermaid-svg-7rupYoBFR6BFRfqS{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-7rupYoBFR6BFRfqS .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-7rupYoBFR6BFRfqS .error-icon{fill:#552222;}#mermaid-svg-7rupYoBFR6BFRfqS .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-7rupYoBFR6BFRfqS .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-7rupYoBFR6BFRfqS .marker{fill:#333333;stroke:#333333;}#mermaid-svg-7rupYoBFR6BFRfqS .marker.cross{stroke:#333333;}#mermaid-svg-7rupYoBFR6BFRfqS svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-7rupYoBFR6BFRfqS p{margin:0;}#mermaid-svg-7rupYoBFR6BFRfqS .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-7rupYoBFR6BFRfqS .cluster-label text{fill:#333;}#mermaid-svg-7rupYoBFR6BFRfqS .cluster-label span{color:#333;}#mermaid-svg-7rupYoBFR6BFRfqS .cluster-label span p{background-color:transparent;}#mermaid-svg-7rupYoBFR6BFRfqS .label text,#mermaid-svg-7rupYoBFR6BFRfqS span{fill:#333;color:#333;}#mermaid-svg-7rupYoBFR6BFRfqS .node rect,#mermaid-svg-7rupYoBFR6BFRfqS .node circle,#mermaid-svg-7rupYoBFR6BFRfqS .node ellipse,#mermaid-svg-7rupYoBFR6BFRfqS .node polygon,#mermaid-svg-7rupYoBFR6BFRfqS .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-7rupYoBFR6BFRfqS .rough-node .label text,#mermaid-svg-7rupYoBFR6BFRfqS .node .label text,#mermaid-svg-7rupYoBFR6BFRfqS .image-shape .label,#mermaid-svg-7rupYoBFR6BFRfqS .icon-shape .label{text-anchor:middle;}#mermaid-svg-7rupYoBFR6BFRfqS .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-7rupYoBFR6BFRfqS .rough-node .label,#mermaid-svg-7rupYoBFR6BFRfqS .node .label,#mermaid-svg-7rupYoBFR6BFRfqS .image-shape .label,#mermaid-svg-7rupYoBFR6BFRfqS .icon-shape .label{text-align:center;}#mermaid-svg-7rupYoBFR6BFRfqS .node.clickable{cursor:pointer;}#mermaid-svg-7rupYoBFR6BFRfqS .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-7rupYoBFR6BFRfqS .arrowheadPath{fill:#333333;}#mermaid-svg-7rupYoBFR6BFRfqS .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-7rupYoBFR6BFRfqS .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-7rupYoBFR6BFRfqS .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7rupYoBFR6BFRfqS .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-7rupYoBFR6BFRfqS .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7rupYoBFR6BFRfqS .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-7rupYoBFR6BFRfqS .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-7rupYoBFR6BFRfqS .cluster text{fill:#333;}#mermaid-svg-7rupYoBFR6BFRfqS .cluster span{color:#333;}#mermaid-svg-7rupYoBFR6BFRfqS div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-7rupYoBFR6BFRfqS .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-7rupYoBFR6BFRfqS rect.text{fill:none;stroke-width:0;}#mermaid-svg-7rupYoBFR6BFRfqS .icon-shape,#mermaid-svg-7rupYoBFR6BFRfqS .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-7rupYoBFR6BFRfqS .icon-shape p,#mermaid-svg-7rupYoBFR6BFRfqS .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-7rupYoBFR6BFRfqS .icon-shape .label rect,#mermaid-svg-7rupYoBFR6BFRfqS .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-7rupYoBFR6BFRfqS .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-7rupYoBFR6BFRfqS .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-7rupYoBFR6BFRfqS :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

n < 47

47 ≤ n

是

是

否

否

是

否

是

否

n > 内存容量

是

是

否 且均匀分布

排序需求

数据量?

插入排序

需要稳定?

内存受限?

稳定快排（需额外空间）

TimSort / 归并排序

内存受限?

堆排序 O(1)空间

数据近乎有序?

插入排序（O(n)）

快排 / IntroSort

外部归并排序

取值范围小?

计数排序 O(n+k)

桶排序

图9-3：工程排序选型决策树——根据数据量、稳定性需求、内存约束选择最优算法

第10章 面试高频题型与实战总结

10.1 题型一：手写排序算法

考点：快速排序的 partition、归并排序的 merge 是最高频的手写题。

例题：手写快速排序（要求三数取中 + 小区间插入排序优化）。

public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length – 1);
}

private static void quickSort(int[] arr, int lo, int hi) {
// 优化1: 小区间用插入排序
if (hi – lo < 16) {
insertionSortRange(arr, lo, hi);
return;
}
// 优化2: 三数取中选pivot
int mid = lo + (hi – lo) / 2;
if (arr[lo] > arr[mid]) swap(arr, lo, mid);
if (arr[lo] > arr[hi]) swap(arr, lo, hi);
if (arr[mid] > arr[hi]) swap(arr, mid, hi);
swap(arr, mid, hi); // 中位数放到arr[hi]

// 优化3: 三路分区（处理大量重复元素）
int pivot = arr[hi];
int lt = lo, gt = hi, i = lo;
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, lt++, i++);
} else if (arr[i] > pivot) {
swap(arr, i, gt—);
} else {
i++;
}
}
// arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
quickSort(arr, lo, lt – 1);
quickSort(arr, gt + 1, hi);
}

private static void insertionSortRange(int[] arr, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++) {
int key = arr[i];
int j = i – 1;
while (j >= lo && arr[j] > key) {
arr[j + 1] = arr[j];
j—;
}
arr[j + 1] = key;
}
}

三路分区（Dutch National Flag）的优势：当有大量重复元素时，标准快排（二路）会把相等的元素分散到两边，重复递归处理。三路分区把相等的元素集中到中间，只递归处理 < pivot 和 > pivot 的部分，对大量重复数据效率显著提升。

10.2 题型二：Top-K 问题

例题：LeetCode 215. 数组中的第K个最大元素。

三种解法，复杂度递减：

解法1：排序 — 先排序再取第k个，O(n log n)。简单但不充分利用问题结构。

解法2：堆 — 维护大小k的小顶堆，O(n log k)。已在第7章给出代码。

解法3：快速选择（QuickSelect） — 利用快排的partition，只递归包含第k大的一侧，平均O(n)。

public static int findKthLargest(int[] nums, int k) {
int target = nums.length – k; // 第k大 = 第(n-k)小（0-indexed）
return quickSelect(nums, 0, nums.length – 1, target);
}

private static int quickSelect(int[] arr, int lo, int hi, int target) {
if (lo == hi) return arr[lo];

int p = partition(arr, lo, hi); // Lomuto分区

if (p == target) {
return arr[p]; // pivot恰好是目标位置
} else if (p < target) {
return quickSelect(arr, p + 1, hi, target); // 只递归右半
} else {
return quickSelect(arr, lo, p – 1, target); // 只递归左半
}
}

QuickSelect为什么是O(n)：每次只递归一侧（不像快排两侧都递归），T(n) = T(n/2) + O(n) = O(n) + O(n/2) + O(n/4) + … = O(2n) = O(n)。但最坏情况O(n²)（pivot选择差），可以用"中位数的中位数"（BFPRT算法）保证最坏O(n)，但常数太大实际很少用。

10.3 题型三：合并有序数组/链表

例题：LeetCode 23. 合并K个升序链表。

解法1：逐一合并 — 依次合并每个链表，O(kN)（k为链表数，N为总节点数）。

解法2：分治合并 — 两两配对合并，O(N log k)。

public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length – 1);
}

private ListNode merge(ListNode[] lists, int lo, int hi) {
if (lo == hi) return lists[lo];
int mid = lo + (hi – lo) / 2;
ListNode left = merge(lists, lo, mid);
ListNode right = merge(lists, mid + 1, hi);
return mergeTwoLists(left, right);
}

解法3：最小堆 — 把每个链表的头节点放入小顶堆，每次取最小，放入该节点后将其后继入堆。O(N log k)。

public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val – b.val);
for (ListNode node : lists) {
if (node != null) pq.offer(node);
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
cur.next = node;
cur = cur.next;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}

10.4 题型四：逆序对计数

例题：LeetCode LCR 170. 数组中的逆序对。

暴力法O(n²)会超时。经典解法是用归并排序统计逆序对，O(n log n)。

private int count = 0;

public int reversePairs(int[] nums) {
count = 0;
int[] temp = new int[nums.length];
mergeSort(nums, 0, nums.length – 1, temp);
return count;
}

private void mergeSort(int[] arr, int lo, int hi, int[] temp) {
if (lo >= hi) return;
int mid = lo + (hi – lo) / 2;
mergeSort(arr, lo, mid, temp);
mergeSort(arr, mid + 1, hi, temp);
mergeAndCount(arr, lo, mid, hi, temp);
}

private void mergeAndCount(int[] arr, int lo, int mid, int hi, int[] temp) {
System.arraycopy(arr, lo, temp, lo, hi – lo + 1);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
// temp[i..mid] 全部 > temp[j]，构成逆序对
count += mid – i + 1;
arr[k++] = temp[j++];
}
}
while (i <= mid) arr[k++] = temp[i++];
while (j <= hi) arr[k++] = temp[j++];
}

关键洞察：在merge过程中，当右半的 temp[j] 小于左半的 temp[i] 时，temp[i..mid] 的所有元素都大于 temp[j]（因为左半已有序），形成 mid – i + 1 个逆序对。这就是归并排序统计逆序对的核心。

10.5 题型五：荷兰国旗问题

例题：LeetCode 75. 颜色分类（0、1、2排序）。

三路分区的经典应用，O(n) 一次遍历完成：

public void sortColors(int[] nums) {
int lo = 0, mid = 0, hi = nums.length – 1;
while (mid <= hi) {
if (nums[mid] == 0) {
swap(nums, lo++, mid++);
} else if (nums[mid] == 1) {
mid++;
} else { // nums[mid] == 2
swap(nums, mid, hi—);
}
}
}

#mermaid-svg-uQFNIcFpT7ZGpcLU{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-uQFNIcFpT7ZGpcLU .error-icon{fill:#552222;}#mermaid-svg-uQFNIcFpT7ZGpcLU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-uQFNIcFpT7ZGpcLU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .marker.cross{stroke:#333333;}#mermaid-svg-uQFNIcFpT7ZGpcLU svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-uQFNIcFpT7ZGpcLU p{margin:0;}#mermaid-svg-uQFNIcFpT7ZGpcLU .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster-label text{fill:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster-label span{color:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster-label span p{background-color:transparent;}#mermaid-svg-uQFNIcFpT7ZGpcLU .label text,#mermaid-svg-uQFNIcFpT7ZGpcLU span{fill:#333;color:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .node rect,#mermaid-svg-uQFNIcFpT7ZGpcLU .node circle,#mermaid-svg-uQFNIcFpT7ZGpcLU .node ellipse,#mermaid-svg-uQFNIcFpT7ZGpcLU .node polygon,#mermaid-svg-uQFNIcFpT7ZGpcLU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .rough-node .label text,#mermaid-svg-uQFNIcFpT7ZGpcLU .node .label text,#mermaid-svg-uQFNIcFpT7ZGpcLU .image-shape .label,#mermaid-svg-uQFNIcFpT7ZGpcLU .icon-shape .label{text-anchor:middle;}#mermaid-svg-uQFNIcFpT7ZGpcLU .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .rough-node .label,#mermaid-svg-uQFNIcFpT7ZGpcLU .node .label,#mermaid-svg-uQFNIcFpT7ZGpcLU .image-shape .label,#mermaid-svg-uQFNIcFpT7ZGpcLU .icon-shape .label{text-align:center;}#mermaid-svg-uQFNIcFpT7ZGpcLU .node.clickable{cursor:pointer;}#mermaid-svg-uQFNIcFpT7ZGpcLU .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .arrowheadPath{fill:#333333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uQFNIcFpT7ZGpcLU .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-uQFNIcFpT7ZGpcLU .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uQFNIcFpT7ZGpcLU .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster text{fill:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU .cluster span{color:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-uQFNIcFpT7ZGpcLU .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-uQFNIcFpT7ZGpcLU rect.text{fill:none;stroke-width:0;}#mermaid-svg-uQFNIcFpT7ZGpcLU .icon-shape,#mermaid-svg-uQFNIcFpT7ZGpcLU .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uQFNIcFpT7ZGpcLU .icon-shape p,#mermaid-svg-uQFNIcFpT7ZGpcLU .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-uQFNIcFpT7ZGpcLU .icon-shape .label rect,#mermaid-svg-uQFNIcFpT7ZGpcLU .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uQFNIcFpT7ZGpcLU .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-uQFNIcFpT7ZGpcLU .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-uQFNIcFpT7ZGpcLU :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

三路分区（荷兰国旗）

[0,0,…,0 | 1,1,…,1 | ? ? ? | 2,2,…,2]

lo: 0的右边界

mid: 当前扫描位置

hi: 2的左边界

lo..mid-1: 全是1mid..hi: 未处理区域

图10-1：荷兰国旗问题三路分区——用三个指针划分0、1、2三个区域

10.6 面试速记总结表

10.7 全文核心知识点回顾

#mermaid-svg-mrSj8cejXdw9UNXb{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-mrSj8cejXdw9UNXb .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-mrSj8cejXdw9UNXb .error-icon{fill:#552222;}#mermaid-svg-mrSj8cejXdw9UNXb .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-mrSj8cejXdw9UNXb .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-mrSj8cejXdw9UNXb .marker{fill:#333333;stroke:#333333;}#mermaid-svg-mrSj8cejXdw9UNXb .marker.cross{stroke:#333333;}#mermaid-svg-mrSj8cejXdw9UNXb svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-mrSj8cejXdw9UNXb p{margin:0;}#mermaid-svg-mrSj8cejXdw9UNXb .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-mrSj8cejXdw9UNXb .cluster-label text{fill:#333;}#mermaid-svg-mrSj8cejXdw9UNXb .cluster-label span{color:#333;}#mermaid-svg-mrSj8cejXdw9UNXb .cluster-label span p{background-color:transparent;}#mermaid-svg-mrSj8cejXdw9UNXb .label text,#mermaid-svg-mrSj8cejXdw9UNXb span{fill:#333;color:#333;}#mermaid-svg-mrSj8cejXdw9UNXb .node rect,#mermaid-svg-mrSj8cejXdw9UNXb .node circle,#mermaid-svg-mrSj8cejXdw9UNXb .node ellipse,#mermaid-svg-mrSj8cejXdw9UNXb .node polygon,#mermaid-svg-mrSj8cejXdw9UNXb .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-mrSj8cejXdw9UNXb .rough-node .label text,#mermaid-svg-mrSj8cejXdw9UNXb .node .label text,#mermaid-svg-mrSj8cejXdw9UNXb .image-shape .label,#mermaid-svg-mrSj8cejXdw9UNXb .icon-shape .label{text-anchor:middle;}#mermaid-svg-mrSj8cejXdw9UNXb .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-mrSj8cejXdw9UNXb .rough-node .label,#mermaid-svg-mrSj8cejXdw9UNXb .node .label,#mermaid-svg-mrSj8cejXdw9UNXb .image-shape .label,#mermaid-svg-mrSj8cejXdw9UNXb .icon-shape .label{text-align:center;}#mermaid-svg-mrSj8cejXdw9UNXb .node.clickable{cursor:pointer;}#mermaid-svg-mrSj8cejXdw9UNXb .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-mrSj8cejXdw9UNXb .arrowheadPath{fill:#333333;}#mermaid-svg-mrSj8cejXdw9UNXb .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-mrSj8cejXdw9UNXb .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-mrSj8cejXdw9UNXb .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mrSj8cejXdw9UNXb .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-mrSj8cejXdw9UNXb .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mrSj8cejXdw9UNXb .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-mrSj8cejXdw9UNXb .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-mrSj8cejXdw9UNXb .cluster text{fill:#333;}#mermaid-svg-mrSj8cejXdw9UNXb .cluster span{color:#333;}#mermaid-svg-mrSj8cejXdw9UNXb div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-mrSj8cejXdw9UNXb .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-mrSj8cejXdw9UNXb rect.text{fill:none;stroke-width:0;}#mermaid-svg-mrSj8cejXdw9UNXb .icon-shape,#mermaid-svg-mrSj8cejXdw9UNXb .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-mrSj8cejXdw9UNXb .icon-shape p,#mermaid-svg-mrSj8cejXdw9UNXb .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-mrSj8cejXdw9UNXb .icon-shape .label rect,#mermaid-svg-mrSj8cejXdw9UNXb .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-mrSj8cejXdw9UNXb .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-mrSj8cejXdw9UNXb .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-mrSj8cejXdw9UNXb :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

排序算法知识体系

排序算法

比较排序 O(n log n)下界

非比较排序 O(n)可突破

O(n²): 冒泡/选择/插入

O(n log n): 归并/快排/堆排

冒泡: 稳定, 优化后最好O(n)

选择: 不稳定, 交换最少

插入: 稳定, 小数组王者

归并: 稳定, 外部排序/链表首选

快排: 不稳定, 实际最快

堆排: 不稳定, Top-K首选

计数: 整数+范围小

基数: 定长数字/字符串

桶: 均匀分布

工程混合策略

TimSort: 归并+插入, 稳定

IntroSort: 快排+堆排+插入, 不稳定

pdqsort: 快排+堆排+插入, Rust/Go

图10-2：排序算法知识体系全景回顾

10.8 一句话记住每个算法

• 冒泡：相邻交换，稳定，最好O(n)
• 选择：找最小值交换，不稳定，交换最少
• 插入：扑克牌插入，稳定，小数组最快
• 归并：分治合并，稳定，外部排序首选
• 快排：分区递归，不稳定，实际最快
• 堆排：建堆取顶，不稳定，Top-K首选
• 计数：统计频次，稳定，范围小才用
• 基数：按位排序，稳定，整数/字符串
• 桶排：分桶排序，稳定，均匀分布才快

全文完。 本文覆盖了9种经典排序算法的原理、执行过程图解、复杂度推导、稳定性证明和工程应用，以及三大主流语言的库实现选型。如果对你有帮助，欢迎点赞收藏。