【排序算法专题·第二章】O(n log n) 双雄:归并排序与快速排序——分治哲学的两种实现,彻底搞懂"分而治之"的排序内核
O(n²) 排序的瓶颈在于"逐个确定位置",每确定一个位置要 O(n) 次比较,n 个位置就是 O(n²)。怎么突破?答案是分治——把大问题拆成小问题,小问题的解合并成大问题的解。归并排序和快速排序是分治思想的两种实现:归并排序"先拆后合",快速排序"先分后治"。它们共享 O(n log n) 的时间复杂度,但性格截然相反——一个稳定但费空间,一个不稳定但极快。面试中排序题的区分度,90% 集中在这两个算法。这篇文章把两者拆到"分治策略"的层面,每种都给出逐帧图解、多种实现、工程优化和 LeetCode 实战。
〇、全文导航
#mermaid-svg-bGmBgqAgRIqNpbly{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-bGmBgqAgRIqNpbly .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-bGmBgqAgRIqNpbly .error-icon{fill:#552222;}#mermaid-svg-bGmBgqAgRIqNpbly .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-bGmBgqAgRIqNpbly .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-bGmBgqAgRIqNpbly .marker{fill:#333333;stroke:#333333;}#mermaid-svg-bGmBgqAgRIqNpbly .marker.cross{stroke:#333333;}#mermaid-svg-bGmBgqAgRIqNpbly svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-bGmBgqAgRIqNpbly p{margin:0;}#mermaid-svg-bGmBgqAgRIqNpbly .edge{stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .section–1 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section–1 path,#mermaid-svg-bGmBgqAgRIqNpbly .section–1 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section–1 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section–1 text{fill:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth–1{stroke-width:17;}#mermaid-svg-bGmBgqAgRIqNpbly .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-0 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-0 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-0 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-0 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-0 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-0{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-0{stroke-width:14;}#mermaid-svg-bGmBgqAgRIqNpbly .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-1 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-1 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-1 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-1 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-1 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-1{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-1{stroke-width:11;}#mermaid-svg-bGmBgqAgRIqNpbly .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-2 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-2 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-2 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-2 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-2 text{fill:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-2{stroke-width:8;}#mermaid-svg-bGmBgqAgRIqNpbly .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-3 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-3 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-3 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-3 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-3 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-3{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-3{stroke-width:5;}#mermaid-svg-bGmBgqAgRIqNpbly .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-4 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-4 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-4 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-4 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-4 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-4{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-4{stroke-width:2;}#mermaid-svg-bGmBgqAgRIqNpbly .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-5 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-5 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-5 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-5 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-5 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-5{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-5{stroke-width:-1;}#mermaid-svg-bGmBgqAgRIqNpbly .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-6 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-6 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-6 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-6 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-6 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-6{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-6{stroke-width:-4;}#mermaid-svg-bGmBgqAgRIqNpbly .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-7 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-7 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-7 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-7 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-7 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-7{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-7{stroke-width:-7;}#mermaid-svg-bGmBgqAgRIqNpbly .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-8 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-8 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-8 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-8 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-8 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-8{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-8{stroke-width:-10;}#mermaid-svg-bGmBgqAgRIqNpbly .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-9 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-9 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-9 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-9 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-9 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-9{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-9{stroke-width:-13;}#mermaid-svg-bGmBgqAgRIqNpbly .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-10 rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-10 path,#mermaid-svg-bGmBgqAgRIqNpbly .section-10 circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-10 polygon,#mermaid-svg-bGmBgqAgRIqNpbly .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-10 text{fill:black;}#mermaid-svg-bGmBgqAgRIqNpbly .node-icon-10{font-size:40px;color:black;}#mermaid-svg-bGmBgqAgRIqNpbly .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .edge-depth-10{stroke-width:-16;}#mermaid-svg-bGmBgqAgRIqNpbly .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled,#mermaid-svg-bGmBgqAgRIqNpbly .disabled circle,#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:lightgray;}#mermaid-svg-bGmBgqAgRIqNpbly .disabled text{fill:#efefef;}#mermaid-svg-bGmBgqAgRIqNpbly .section-root rect,#mermaid-svg-bGmBgqAgRIqNpbly .section-root path,#mermaid-svg-bGmBgqAgRIqNpbly .section-root circle,#mermaid-svg-bGmBgqAgRIqNpbly .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-bGmBgqAgRIqNpbly .section-root text{fill:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .section-root span{color:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .section-2 span{color:#ffffff;}#mermaid-svg-bGmBgqAgRIqNpbly .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-bGmBgqAgRIqNpbly .edge{fill:none;}#mermaid-svg-bGmBgqAgRIqNpbly .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-bGmBgqAgRIqNpbly :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
O(n log n)排序·深度剖析
分治思想
分治三步法
递归树与复杂度
两种分治策略
归并排序
核心思想 先拆后合
数组实现 递归+迭代
链表实现 归并天然适配
稳定性分析
工程应用
快速排序
核心思想 先分后治
Lomuto分区
Hoare分区
随机化与三路分区
工程优化5板斧
终极对比
10维度对比
工程选型指南
面试怎么答
LeetCode实战
排序链表
数组中第K大
合并区间
逆序对
一、分治思想:O(n log n) 的理论根基
1.1 从 O(n²) 到 O(n log n):一次认知跃迁
O(n²) 排序的共同特征:每轮只确定一个元素的最终位置,需要 n 轮,每轮 O(n)。
分治的突破点:不逐个确定,而是把问题对半拆分。
O(n²) 思路: [3,1,4,1,5,9,2,6] → 确定最小值 → 确定次小值 → …
每一步 O(n),共 n 步 → O(n²)
分治思路: [3,1,4,1,5,9,2,6]
↙ ↘
[3,1,4,1] [5,9,2,6] ← 拆:O(1)
↙ ↘ ↙ ↘
[3,1] [4,1] [5,9] [2,6] ← 拆:O(1)
↙ ↘ ↙ ↘ ↙ ↘ ↙ ↘
3 1 4 1 5 9 2 6 ← 拆到最小
↘ ↙ ↘ ↙ ↘ ↙ ↘ ↙
[1,3] [1,4] [5,9] [2,6] ← 合:O(n)
↘ ↙ ↘ ↙
[1,1,3,4] [2,5,6,9] ← 合:O(n)
↘ ↙
[1,1,2,3,4,5,6,9] ← 合:O(n)
关键洞察:拆分 O(1)(只需找中点),合并 O(n)(双指针归并),共 log n 层,总 O(n log n)。
1.2 递归树与复杂度推导
#mermaid-svg-wMG6Do79SRYGvZbK{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-wMG6Do79SRYGvZbK .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-wMG6Do79SRYGvZbK .error-icon{fill:#552222;}#mermaid-svg-wMG6Do79SRYGvZbK .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-wMG6Do79SRYGvZbK .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-wMG6Do79SRYGvZbK .marker{fill:#333333;stroke:#333333;}#mermaid-svg-wMG6Do79SRYGvZbK .marker.cross{stroke:#333333;}#mermaid-svg-wMG6Do79SRYGvZbK svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-wMG6Do79SRYGvZbK p{margin:0;}#mermaid-svg-wMG6Do79SRYGvZbK .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-wMG6Do79SRYGvZbK .cluster-label text{fill:#333;}#mermaid-svg-wMG6Do79SRYGvZbK .cluster-label span{color:#333;}#mermaid-svg-wMG6Do79SRYGvZbK .cluster-label span p{background-color:transparent;}#mermaid-svg-wMG6Do79SRYGvZbK .label text,#mermaid-svg-wMG6Do79SRYGvZbK span{fill:#333;color:#333;}#mermaid-svg-wMG6Do79SRYGvZbK .node rect,#mermaid-svg-wMG6Do79SRYGvZbK .node circle,#mermaid-svg-wMG6Do79SRYGvZbK .node ellipse,#mermaid-svg-wMG6Do79SRYGvZbK .node polygon,#mermaid-svg-wMG6Do79SRYGvZbK .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-wMG6Do79SRYGvZbK .rough-node .label text,#mermaid-svg-wMG6Do79SRYGvZbK .node .label text,#mermaid-svg-wMG6Do79SRYGvZbK .image-shape .label,#mermaid-svg-wMG6Do79SRYGvZbK .icon-shape .label{text-anchor:middle;}#mermaid-svg-wMG6Do79SRYGvZbK .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-wMG6Do79SRYGvZbK .rough-node .label,#mermaid-svg-wMG6Do79SRYGvZbK .node .label,#mermaid-svg-wMG6Do79SRYGvZbK .image-shape .label,#mermaid-svg-wMG6Do79SRYGvZbK .icon-shape .label{text-align:center;}#mermaid-svg-wMG6Do79SRYGvZbK .node.clickable{cursor:pointer;}#mermaid-svg-wMG6Do79SRYGvZbK .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-wMG6Do79SRYGvZbK .arrowheadPath{fill:#333333;}#mermaid-svg-wMG6Do79SRYGvZbK .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-wMG6Do79SRYGvZbK .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-wMG6Do79SRYGvZbK .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-wMG6Do79SRYGvZbK .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-wMG6Do79SRYGvZbK .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-wMG6Do79SRYGvZbK .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-wMG6Do79SRYGvZbK .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-wMG6Do79SRYGvZbK .cluster text{fill:#333;}#mermaid-svg-wMG6Do79SRYGvZbK .cluster span{color:#333;}#mermaid-svg-wMG6Do79SRYGvZbK 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-wMG6Do79SRYGvZbK .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-wMG6Do79SRYGvZbK rect.text{fill:none;stroke-width:0;}#mermaid-svg-wMG6Do79SRYGvZbK .icon-shape,#mermaid-svg-wMG6Do79SRYGvZbK .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-wMG6Do79SRYGvZbK .icon-shape p,#mermaid-svg-wMG6Do79SRYGvZbK .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-wMG6Do79SRYGvZbK .icon-shape .label rect,#mermaid-svg-wMG6Do79SRYGvZbK .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-wMG6Do79SRYGvZbK .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-wMG6Do79SRYGvZbK .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-wMG6Do79SRYGvZbK :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
复杂度计算
第0层: n
第1层: n/2 + n/2 = n
第2层: n/4 × 4 = n
共 log n 层
总代价 = n × log n = O(n log n)
归并排序递归树
[n] 代价=n
[n/2] 代价=n/2
[n/2] 代价=n/2
[n/4] 代价=n/4
[n/4] 代价=n/4
[n/4] 代价=n/4
[n/4] 代价=n/4
每一层的总工作量都是 n(分成几块无所谓,合并的总工作量不变),共 log n 层,所以总 O(n log n)。
1.3 两种分治策略:归并 vs 快排
| 分治策略 | 先拆后合(easy split, hard join) | 先分后治(hard split, easy join) |
| 拆分方式 | 直接取中点,O(1) | 选基准分区,O(n) |
| 合并方式 | 双指针归并,O(n) | 无需合并,分区完就排好 |
| 额外空间 | 需要 O(n) 辅助数组 | 原地分区,O(log n) 栈空间 |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 |
| 最坏情况 | O(n log n),始终稳定 | O(n²),退化风险 |
#mermaid-svg-gRRM1HdBnbmGIOAy{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-gRRM1HdBnbmGIOAy .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-gRRM1HdBnbmGIOAy .error-icon{fill:#552222;}#mermaid-svg-gRRM1HdBnbmGIOAy .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-gRRM1HdBnbmGIOAy .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-gRRM1HdBnbmGIOAy .marker{fill:#333333;stroke:#333333;}#mermaid-svg-gRRM1HdBnbmGIOAy .marker.cross{stroke:#333333;}#mermaid-svg-gRRM1HdBnbmGIOAy svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-gRRM1HdBnbmGIOAy p{margin:0;}#mermaid-svg-gRRM1HdBnbmGIOAy .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster-label text{fill:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster-label span{color:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster-label span p{background-color:transparent;}#mermaid-svg-gRRM1HdBnbmGIOAy .label text,#mermaid-svg-gRRM1HdBnbmGIOAy span{fill:#333;color:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy .node rect,#mermaid-svg-gRRM1HdBnbmGIOAy .node circle,#mermaid-svg-gRRM1HdBnbmGIOAy .node ellipse,#mermaid-svg-gRRM1HdBnbmGIOAy .node polygon,#mermaid-svg-gRRM1HdBnbmGIOAy .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-gRRM1HdBnbmGIOAy .rough-node .label text,#mermaid-svg-gRRM1HdBnbmGIOAy .node .label text,#mermaid-svg-gRRM1HdBnbmGIOAy .image-shape .label,#mermaid-svg-gRRM1HdBnbmGIOAy .icon-shape .label{text-anchor:middle;}#mermaid-svg-gRRM1HdBnbmGIOAy .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-gRRM1HdBnbmGIOAy .rough-node .label,#mermaid-svg-gRRM1HdBnbmGIOAy .node .label,#mermaid-svg-gRRM1HdBnbmGIOAy .image-shape .label,#mermaid-svg-gRRM1HdBnbmGIOAy .icon-shape .label{text-align:center;}#mermaid-svg-gRRM1HdBnbmGIOAy .node.clickable{cursor:pointer;}#mermaid-svg-gRRM1HdBnbmGIOAy .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-gRRM1HdBnbmGIOAy .arrowheadPath{fill:#333333;}#mermaid-svg-gRRM1HdBnbmGIOAy .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-gRRM1HdBnbmGIOAy .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-gRRM1HdBnbmGIOAy .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-gRRM1HdBnbmGIOAy .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-gRRM1HdBnbmGIOAy .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-gRRM1HdBnbmGIOAy .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster text{fill:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy .cluster span{color:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy 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-gRRM1HdBnbmGIOAy .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-gRRM1HdBnbmGIOAy rect.text{fill:none;stroke-width:0;}#mermaid-svg-gRRM1HdBnbmGIOAy .icon-shape,#mermaid-svg-gRRM1HdBnbmGIOAy .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-gRRM1HdBnbmGIOAy .icon-shape p,#mermaid-svg-gRRM1HdBnbmGIOAy .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-gRRM1HdBnbmGIOAy .icon-shape .label rect,#mermaid-svg-gRRM1HdBnbmGIOAy .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-gRRM1HdBnbmGIOAy .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-gRRM1HdBnbmGIOAy .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-gRRM1HdBnbmGIOAy :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
快速排序: 先分后治
分: O(n) 选基准分区
基准就位
递归排序左右无需合并
归并排序: 先拆后合
拆: O(1) 取中点
递归排序左右
合: O(n) 双指针归并
一句话区分:归并的难点在"合",快排的难点在"分"。
二、归并排序:分治的"教科书"
2.1 核心思想与不变量
循环不变量:每次 merge 操作后,arr[left..right] 是有序的。
三步走:
2.2 逐帧图解:merge 过程
排序 [5, 2, 4, 7, 1, 3, 2, 6],重点看最后一层 merge:
递归到底后,开始自底向上合并:
第1层合并(长度1→2):
[5] [2] → [2, 5] [4] [7] → [4, 7] [1] [3] → [1, 3] [2] [6] → [2, 6]
第2层合并(长度2→4):
[2, 5] [4, 7] → [2, 4, 5, 7] [1, 3] [2, 6] → [1, 2, 3, 6]
第3层合并(长度4→8):
[2, 4, 5, 7] [1, 2, 3, 6] → ?
最后一层 merge 的详细过程:
左半: [2, 4, 5, 7] 右半: [1, 2, 3, 6] 辅助数组: []
Step 1: i=0, j=0 → 左[0]=2 > 右[0]=1 → 取右[0]=1
左: [2, 4, 5, 7] 右: [_, 2, 3, 6] 结果: [1]
Step 2: i=0, j=1 → 左[0]=2 ≤ 右[1]=2 → 取左[0]=2(相等取左,保证稳定性!)
左: [_, 4, 5, 7] 右: [_, 2, 3, 6] 结果: [1, 2]
Step 3: i=1, j=1 → 左[1]=4 > 右[1]=2 → 取右[1]=2
左: [_, 4, 5, 7] 右: [_, _, 3, 6] 结果: [1, 2, 2]
Step 4: i=1, j=2 → 左[1]=4 > 右[2]=3 → 取右[2]=3
左: [_, 4, 5, 7] 右: [_, _, _, 6] 结果: [1, 2, 2, 3]
Step 5: i=1, j=3 → 左[1]=4 ≤ 右[3]=6 → 取左[1]=4
左: [_, _, 5, 7] 右: [_, _, _, 6] 结果: [1, 2, 2, 3, 4]
Step 6: i=2, j=3 → 左[2]=5 ≤ 右[3]=6 → 取左[2]=5
左: [_, _, _, 7] 右: [_, _, _, 6] 结果: [1, 2, 2, 3, 4, 5]
Step 7: i=3, j=3 → 左[3]=7 > 右[3]=6 → 取右[3]=6
左: [_, _, _, 7] 右: [_, _, _, _] 结果: [1, 2, 2, 3, 4, 5, 6]
Step 8: 右半耗尽,左半剩余 [7] 直接追加
结果: [1, 2, 2, 3, 4, 5, 6, 7] ✅
稳定性关键:当 left[i] == right[j] 时,取左半的元素——这保证了相等元素的原始相对顺序不变。
2.3 数组实现(递归版)
public class MergeSort {
private static int[] temp; // 辅助数组,全局分配一次
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
temp = new int[arr.length]; // 只分配一次,避免递归中反复创建
mergeSort(arr, 0, arr.length – 1);
}
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return; // 递归终止:只有一个元素
int mid = left + (right – left) / 2; // 防溢出写法
mergeSort(arr, left, mid); // 排左半
mergeSort(arr, mid + 1, right); // 排右半
merge(arr, left, mid, right); // 合并
}
private static void merge(int[] arr, int left, int mid, int right) {
// 1. 拷贝到辅助数组
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
// 2. 双指针归并
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) { // 左半耗尽
arr[k] = temp[j++];
} else if (j > right) { // 右半耗尽
arr[k] = temp[i++];
} else if (temp[i] <= temp[j]) { // 相等取左,保证稳定性
arr[k] = temp[i++];
} else {
arr[k] = temp[j++];
}
}
}
}
三个关键细节:
| 中点计算 | left + (right – left) / 2 | 防止 (left + right) 溢出 |
| 辅助数组 | 全局分配一次 | 避免每次 merge 创建新数组 |
| 相等取左 | temp[i] <= temp[j] | 保证稳定性 |
2.4 数组实现(迭代版 / 自底向上)
递归版有栈空间开销 O(log n),迭代版完全消除递归:
public static void sortIterative(int[] arr) {
int n = arr.length;
temp = new int[n];
// width 从 1 开始倍增: 1 → 2 → 4 → 8 → …
for (int width = 1; width < n; width *= 2) {
for (int left = 0; left < n; left += 2 * width) {
int mid = Math.min(left + width – 1, n – 1);
int right = Math.min(left + 2 * width – 1, n – 1);
if (mid < right) { // 确保有右半可合并
merge(arr, left, mid, right);
}
}
}
}
迭代版的优势:无递归栈,空间严格 O(n),适合对栈深度敏感的场景。
2.5 链表实现:归并排序的天然主场
为什么归并排序特别适合链表?
| 找中点 | O(1),直接算下标 | O(n),快慢指针 |
| 拆分 | O(1),用下标划分 | O(1),断开链表 |
| 合并 | O(n),需要辅助数组 | O(1) 额外空间,改指针即可 |
| 随机访问 | 需要 | 不需要 |
链表归并排序是 O(n log n) 时间 + O(1) 额外空间的排序——这是链表排序的理论最优。
public ListNode sortList(ListNode head) {
// 递归终止:空或单节点
if (head == null || head.next == null) return head;
// 1. 快慢指针找中点
ListNode slow = head, fast = head.next; // fast从head.next开始
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 断开链表
ListNode rightHead = slow.next;
slow.next = null; // 关键:断开!
// 3. 递归排序左右半
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
// 4. 合并两个有序链表
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) { // 相等取l1,保证稳定性
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;
}
链表归并的三个关键细节:
| fast 起始位置 | fast = head.next | 偶数节点时 slow 停在左半末尾 |
| 断开链表 | slow.next = null | 不断开会死循环 |
| 哨兵节点 | dummy | 消除头节点特殊处理 |
#mermaid-svg-2zEqmaZp9HSZqaFk{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-2zEqmaZp9HSZqaFk .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-2zEqmaZp9HSZqaFk .error-icon{fill:#552222;}#mermaid-svg-2zEqmaZp9HSZqaFk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-2zEqmaZp9HSZqaFk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-2zEqmaZp9HSZqaFk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-2zEqmaZp9HSZqaFk .marker.cross{stroke:#333333;}#mermaid-svg-2zEqmaZp9HSZqaFk svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-2zEqmaZp9HSZqaFk p{margin:0;}#mermaid-svg-2zEqmaZp9HSZqaFk .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster-label text{fill:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster-label span{color:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster-label span p{background-color:transparent;}#mermaid-svg-2zEqmaZp9HSZqaFk .label text,#mermaid-svg-2zEqmaZp9HSZqaFk span{fill:#333;color:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk .node rect,#mermaid-svg-2zEqmaZp9HSZqaFk .node circle,#mermaid-svg-2zEqmaZp9HSZqaFk .node ellipse,#mermaid-svg-2zEqmaZp9HSZqaFk .node polygon,#mermaid-svg-2zEqmaZp9HSZqaFk .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-2zEqmaZp9HSZqaFk .rough-node .label text,#mermaid-svg-2zEqmaZp9HSZqaFk .node .label text,#mermaid-svg-2zEqmaZp9HSZqaFk .image-shape .label,#mermaid-svg-2zEqmaZp9HSZqaFk .icon-shape .label{text-anchor:middle;}#mermaid-svg-2zEqmaZp9HSZqaFk .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-2zEqmaZp9HSZqaFk .rough-node .label,#mermaid-svg-2zEqmaZp9HSZqaFk .node .label,#mermaid-svg-2zEqmaZp9HSZqaFk .image-shape .label,#mermaid-svg-2zEqmaZp9HSZqaFk .icon-shape .label{text-align:center;}#mermaid-svg-2zEqmaZp9HSZqaFk .node.clickable{cursor:pointer;}#mermaid-svg-2zEqmaZp9HSZqaFk .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-2zEqmaZp9HSZqaFk .arrowheadPath{fill:#333333;}#mermaid-svg-2zEqmaZp9HSZqaFk .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-2zEqmaZp9HSZqaFk .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-2zEqmaZp9HSZqaFk .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-2zEqmaZp9HSZqaFk .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-2zEqmaZp9HSZqaFk .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-2zEqmaZp9HSZqaFk .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster text{fill:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk .cluster span{color:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk 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-2zEqmaZp9HSZqaFk .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-2zEqmaZp9HSZqaFk rect.text{fill:none;stroke-width:0;}#mermaid-svg-2zEqmaZp9HSZqaFk .icon-shape,#mermaid-svg-2zEqmaZp9HSZqaFk .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-2zEqmaZp9HSZqaFk .icon-shape p,#mermaid-svg-2zEqmaZp9HSZqaFk .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-2zEqmaZp9HSZqaFk .icon-shape .label rect,#mermaid-svg-2zEqmaZp9HSZqaFk .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-2zEqmaZp9HSZqaFk .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-2zEqmaZp9HSZqaFk .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-2zEqmaZp9HSZqaFk :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
4 → 2 → 1 → 3
快慢指针找中点
slow=2, fast=3
断开: 4→2 和 1→3
递归排序左半: 2→4
递归排序右半: 1→3
合并: 1→2→3→4
2.6 归并排序的工程应用
| Java 对象排序 | Arrays.sort(Object[]) | 对象排序需要稳定性 |
| Python sorted | sorted() / list.sort() | TimSort = 归并 + 插入 |
| 大文件外部排序 | 数据量超过内存 | 归并可分块排序再合并 |
| 链表排序 | LeetCode 148 | O(1) 额外空间 |
| 逆序对计数 | LeetCode 493 | merge 时统计跨越两半的逆序对 |
三、快速排序:工程中最快的排序
3.1 核心思想与不变量
循环不变量:每次 partition 后,基准元素 pivot 在其最终位置,左边都 ≤ pivot,右边都 > pivot。
三步走:
3.2 Lomuto 分区方案(易懂版)
Lomuto 方案用单指针从左到右扫描,维护一个分界线:
不变量: arr[left..i] ≤ pivot < arr[i+1..j-1], arr[j..right] 未处理
初始: [pivot | ← 未处理 →]
left i j right
扫描: [≤ pivot | > pivot | ← 未处理 →]
left i j right
最终: [≤ pivot | pivot | > pivot]
left k-1 k right
// Lomuto 分区:选最右元素为 pivot
private static int partitionLomuto(int[] arr, int left, int right) {
int pivot = arr[right]; // 选最右为基准
int i = left – 1; // i 指向 ≤ pivot 区域的末尾
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) { // 当前元素 ≤ pivot
i++;
swap(arr, i, j); // 扩展 ≤ pivot 区域
}
}
swap(arr, i + 1, right); // pivot 归位
return i + 1; // 返回 pivot 最终位置
}
逐帧图解:对 [3, 6, 2, 8, 5, 1, 4, 7],pivot = 7(最右)
初始: [3, 6, 2, 8, 5, 1, 4, 7] pivot=7, i=-1
j=0: 3≤7 → i=0, swap(0,0) → [3, 6, 2, 8, 5, 1, 4, 7]
j=1: 6≤7 → i=1, swap(1,1) → [3, 6, 2, 8, 5, 1, 4, 7]
j=2: 2≤7 → i=2, swap(2,2) → [3, 6, 2, 8, 5, 1, 4, 7]
j=3: 8>7 → 跳过 [3, 6, 2, 8, 5, 1, 4, 7]
j=4: 5≤7 → i=3, swap(3,4) → [3, 6, 2, 5, 8, 1, 4, 7]
j=5: 1≤7 → i=4, swap(4,5) → [3, 6, 2, 5, 1, 8, 4, 7]
j=6: 4≤7 → i=5, swap(5,6) → [3, 6, 2, 5, 1, 4, 8, 7]
最后: swap(i+1, right) → swap(6,7) → [3, 6, 2, 5, 1, 4, 7, 8]
≤7 ──────→ 7 ←8
pivot=7 在位置6,左边都≤7,右边>7 ✅
3.3 Hoare 分区方案(高效版)
Hoare 方案用双指针从两端向中间靠拢,交换逆序对:
// Hoare 分区:双指针对向扫描
private static int partitionHoare(int[] arr, int left, int right) {
int pivot = arr[left + (right – left) / 2]; // 选中间元素为基准
int i = left – 1, j = right + 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); // 交换逆序对
}
}
Lomuto vs Hoare 对比:
| 扫描方式 | 单指针左→右 | 双指针两端→中间 |
| 交换次数 | 较多 | 较少(平均少3倍) |
| pivot 位置 | 精确返回 pivot 最终位置 | 返回分界线 |
| 退化风险 | 已排序数组必退化 | 已排序数组不退化 |
| 实际性能 | 较慢 | 较快 |
面试回答:工程实现用 Hoare 分区,教学演示用 Lomuto 分区。
3.4 快排的致命问题:O(n²) 退化
什么情况会退化?
| 已排序数组 + 选首/尾为pivot | 每次分区极不均匀 | 确定性退化 |
| 大量重复元素 | 所有元素等于pivot,分区不均匀 | 确定性退化 |
| 手动构造的恶意输入 | 攻击者知道你选首元素为pivot | 安全风险 |
#mermaid-svg-1LXr8tMtPLJncoQA{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-1LXr8tMtPLJncoQA .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-1LXr8tMtPLJncoQA .error-icon{fill:#552222;}#mermaid-svg-1LXr8tMtPLJncoQA .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1LXr8tMtPLJncoQA .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1LXr8tMtPLJncoQA .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1LXr8tMtPLJncoQA .marker.cross{stroke:#333333;}#mermaid-svg-1LXr8tMtPLJncoQA svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1LXr8tMtPLJncoQA p{margin:0;}#mermaid-svg-1LXr8tMtPLJncoQA .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-1LXr8tMtPLJncoQA .cluster-label text{fill:#333;}#mermaid-svg-1LXr8tMtPLJncoQA .cluster-label span{color:#333;}#mermaid-svg-1LXr8tMtPLJncoQA .cluster-label span p{background-color:transparent;}#mermaid-svg-1LXr8tMtPLJncoQA .label text,#mermaid-svg-1LXr8tMtPLJncoQA span{fill:#333;color:#333;}#mermaid-svg-1LXr8tMtPLJncoQA .node rect,#mermaid-svg-1LXr8tMtPLJncoQA .node circle,#mermaid-svg-1LXr8tMtPLJncoQA .node ellipse,#mermaid-svg-1LXr8tMtPLJncoQA .node polygon,#mermaid-svg-1LXr8tMtPLJncoQA .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1LXr8tMtPLJncoQA .rough-node .label text,#mermaid-svg-1LXr8tMtPLJncoQA .node .label text,#mermaid-svg-1LXr8tMtPLJncoQA .image-shape .label,#mermaid-svg-1LXr8tMtPLJncoQA .icon-shape .label{text-anchor:middle;}#mermaid-svg-1LXr8tMtPLJncoQA .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-1LXr8tMtPLJncoQA .rough-node .label,#mermaid-svg-1LXr8tMtPLJncoQA .node .label,#mermaid-svg-1LXr8tMtPLJncoQA .image-shape .label,#mermaid-svg-1LXr8tMtPLJncoQA .icon-shape .label{text-align:center;}#mermaid-svg-1LXr8tMtPLJncoQA .node.clickable{cursor:pointer;}#mermaid-svg-1LXr8tMtPLJncoQA .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-1LXr8tMtPLJncoQA .arrowheadPath{fill:#333333;}#mermaid-svg-1LXr8tMtPLJncoQA .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-1LXr8tMtPLJncoQA .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-1LXr8tMtPLJncoQA .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-1LXr8tMtPLJncoQA .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-1LXr8tMtPLJncoQA .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-1LXr8tMtPLJncoQA .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-1LXr8tMtPLJncoQA .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-1LXr8tMtPLJncoQA .cluster text{fill:#333;}#mermaid-svg-1LXr8tMtPLJncoQA .cluster span{color:#333;}#mermaid-svg-1LXr8tMtPLJncoQA 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-1LXr8tMtPLJncoQA .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-1LXr8tMtPLJncoQA rect.text{fill:none;stroke-width:0;}#mermaid-svg-1LXr8tMtPLJncoQA .icon-shape,#mermaid-svg-1LXr8tMtPLJncoQA .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-1LXr8tMtPLJncoQA .icon-shape p,#mermaid-svg-1LXr8tMtPLJncoQA .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-1LXr8tMtPLJncoQA .icon-shape .label rect,#mermaid-svg-1LXr8tMtPLJncoQA .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-1LXr8tMtPLJncoQA .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-1LXr8tMtPLJncoQA .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-1LXr8tMtPLJncoQA :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
正常: 随机选pivot
[1,2,3,4,5,6,7,8] pivot=4
[1,2,3] 和 [5,6,7,8] 每次约减半
O(n log n)
退化: 已排序 + 选首元素为pivot
[1,2,3,4,5,6,7,8] pivot=1
[2,3,4,5,6,7,8] pivot=2
[3,4,5,6,7,8] pivot=3
…
每次只减少1个元素 → O(n²)
3.5 优化一:随机化 pivot
private static int partitionRandom(int[] arr, int left, int right) {
// 随机选一个位置,与 right 交换
int randIdx = left + new Random().nextInt(right – left + 1);
swap(arr, randIdx, right);
// 然后用 Lomuto 分区
return partitionLomuto(arr, left, right);
}
为什么随机化能避免退化?
- 确定性输入无法构造恶意数据(攻击者不知道你会选哪个 pivot)
- 期望每次分区近似均匀 → 期望 O(n log n)
- 任何单次输入的期望复杂度都是 O(n log n)
3.6 优化二:三路分区(大量重复元素)
当数组中有大量重复元素时,标准分区会把所有等于 pivot 的元素分到一边。三路分区将数组分为小于、等于、大于三部分:
// 三路分区: Dutch National Flag
private static void quickSort3Way(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left + (right – left) / 2];
int lt = left; // arr[left..lt-1] < pivot
int gt = right; // arr[gt+1..right] > pivot
int i = left; // arr[lt..i-1] = pivot
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, i++, lt++);
} else if (arr[i] > pivot) {
swap(arr, i, gt—);
} else {
i++; // 等于pivot,跳过
}
}
// 现在: [ < pivot | == pivot | > pivot ]
// left..lt-1 lt..gt gt+1..right
quickSort3Way(arr, left, lt – 1);
quickSort3Way(arr, gt + 1, right);
// == pivot 部分已经就位,不需要再排!
}
三路分区逐帧图解:对 [3, 1, 4, 1, 5, 9, 2, 6],pivot = 4
初始: [3, 1, 4, 1, 5, 9, 2, 6] lt=0, i=0, gt=7
i=0: 3<4 → swap(0,0), i++, lt++ → [3, 1, 4, 1, 5, 9, 2, 6] lt=1,i=1
i=1: 1<4 → swap(1,1), i++, lt++ → [3, 1, 4, 1, 5, 9, 2, 6] lt=2,i=2
i=2: 4=4 → i++ → [3, 1, 4, 1, 5, 9, 2, 6] lt=2,i=3
i=3: 1<4 → swap(3,2), i++, lt++ → [3, 1, 1, 4, 5, 9, 2, 6] lt=3,i=4
i=4: 5>4 → swap(4,7), gt– → [3, 1, 1, 4, 6, 9, 2, 5] lt=3,i=4,gt=6
i=4: 6>4 → swap(4,6), gt– → [3, 1, 1, 4, 2, 9, 6, 5] lt=3,i=4,gt=5
i=4: 2<4 → swap(4,3), i++, lt++ → [3, 1, 1, 2, 4, 9, 6, 5] lt=4,i=5
i=5: 9>4 → swap(5,5), gt– → [3, 1, 1, 2, 4, 5, 6, 9] lt=4,i=5,gt=4
i>gt → 结束
结果: [3, 1, 1, 2 | 4 | 5, 6, 9]
< 4 ────→ =4 >4 ──→
三路分区的威力:当所有元素都相同时,一次分区就完成排序——O(n)!
3.7 优化三:插入排序 cutoff
当子数组长度很小时(通常 ≤ 16),快排的递归开销比排序本身还大。此时切换到插入排序:
private static final int INSERTION_THRESHOLD = 16;
private static void quickSortOptimized(int[] arr, int left, int right) {
if (right – left <= INSERTION_THRESHOLD) {
insertionSort(arr, left, right);
return;
}
int p = partitionHoare(arr, left, right);
quickSortOptimized(arr, left, p);
quickSortOptimized(arr, p + 1, right);
}
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i – 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j—;
}
arr[j + 1] = key;
}
}
3.8 快排工程优化五板斧总结
| ① 随机化 pivot | 已排序/恶意输入退化 | 期望 O(n log n) |
| ② 三路分区 | 大量重复元素退化 | 全相同 O(n) |
| ③ 插入排序 cutoff | 小数组递归开销大 | 减少约 15% 操作 |
| ④ Hoare 分区 | Lomuto 交换次数多 | 交换减少约 3 倍 |
| ⑤ 尾递归优化 | 栈深度 O(n) 风险 | 栈深度降至 O(log n) |
尾递归优化:总是先递归较短的一半,较长的一半用循环处理:
private static void quickSortTailRecursive(int[] arr, int left, int right) {
while (left < right) {
int p = partitionHoare(arr, left, right);
if (p – left < right – p) {
quickSortTailRecursive(arr, left, p); // 先递归短半
left = p + 1; // 长半用循环
} else {
quickSortTailRecursive(arr, p + 1, right);
right = p;
}
}
}
3.9 快排的工程应用
| Java 基本类型排序 | Arrays.sort(int[]) | 基本类型不需要稳定性,快排更快 |
| C++ std::sort | 通用排序 | IntroSort = 快排 + 堆排 + 插入 |
| 第K大/小元素 | LeetCode 215 | 快速选择,期望 O(n) |
| 颜色分类 | LeetCode 75 | 三路分区 |
四、终极对比:归并 vs 快排
4.1 十维度对比
| 最好时间 | O(n log n) | O(n log n) |
| 平均时间 | O(n log n) | O(n log n) |
| 最坏时间 | O(n log n) | O(n²) |
| 空间复杂度 | O(n) | O(log n) |
| 稳定性 | ✅ 稳定 | ❌ 不稳定 |
| 原地性 | ❌ 需辅助数组 | ✅ 原地分区 |
| 自适应性 | ❌ 不自适应 | ✅ 随机化后期望均匀 |
| Cache 友好 | 中等(顺序访问) | 好(局部交换) |
| 适合链表 | ✅ 天然适配 | ❌ 不适合(无法随机访问) |
| 并行性 | ✅ 天然并行 | ❌ 分区依赖顺序 |
4.2 工程选型指南
#mermaid-svg-wNIV2ri0VfaIfTmg{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-wNIV2ri0VfaIfTmg .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-wNIV2ri0VfaIfTmg .error-icon{fill:#552222;}#mermaid-svg-wNIV2ri0VfaIfTmg .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-wNIV2ri0VfaIfTmg .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-wNIV2ri0VfaIfTmg .marker{fill:#333333;stroke:#333333;}#mermaid-svg-wNIV2ri0VfaIfTmg .marker.cross{stroke:#333333;}#mermaid-svg-wNIV2ri0VfaIfTmg svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-wNIV2ri0VfaIfTmg p{margin:0;}#mermaid-svg-wNIV2ri0VfaIfTmg .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster-label text{fill:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster-label span{color:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster-label span p{background-color:transparent;}#mermaid-svg-wNIV2ri0VfaIfTmg .label text,#mermaid-svg-wNIV2ri0VfaIfTmg span{fill:#333;color:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg .node rect,#mermaid-svg-wNIV2ri0VfaIfTmg .node circle,#mermaid-svg-wNIV2ri0VfaIfTmg .node ellipse,#mermaid-svg-wNIV2ri0VfaIfTmg .node polygon,#mermaid-svg-wNIV2ri0VfaIfTmg .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-wNIV2ri0VfaIfTmg .rough-node .label text,#mermaid-svg-wNIV2ri0VfaIfTmg .node .label text,#mermaid-svg-wNIV2ri0VfaIfTmg .image-shape .label,#mermaid-svg-wNIV2ri0VfaIfTmg .icon-shape .label{text-anchor:middle;}#mermaid-svg-wNIV2ri0VfaIfTmg .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-wNIV2ri0VfaIfTmg .rough-node .label,#mermaid-svg-wNIV2ri0VfaIfTmg .node .label,#mermaid-svg-wNIV2ri0VfaIfTmg .image-shape .label,#mermaid-svg-wNIV2ri0VfaIfTmg .icon-shape .label{text-align:center;}#mermaid-svg-wNIV2ri0VfaIfTmg .node.clickable{cursor:pointer;}#mermaid-svg-wNIV2ri0VfaIfTmg .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-wNIV2ri0VfaIfTmg .arrowheadPath{fill:#333333;}#mermaid-svg-wNIV2ri0VfaIfTmg .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-wNIV2ri0VfaIfTmg .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-wNIV2ri0VfaIfTmg .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-wNIV2ri0VfaIfTmg .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-wNIV2ri0VfaIfTmg .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-wNIV2ri0VfaIfTmg .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster text{fill:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg .cluster span{color:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg 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-wNIV2ri0VfaIfTmg .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-wNIV2ri0VfaIfTmg rect.text{fill:none;stroke-width:0;}#mermaid-svg-wNIV2ri0VfaIfTmg .icon-shape,#mermaid-svg-wNIV2ri0VfaIfTmg .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-wNIV2ri0VfaIfTmg .icon-shape p,#mermaid-svg-wNIV2ri0VfaIfTmg .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-wNIV2ri0VfaIfTmg .icon-shape .label rect,#mermaid-svg-wNIV2ri0VfaIfTmg .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-wNIV2ri0VfaIfTmg .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-wNIV2ri0VfaIfTmg .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-wNIV2ri0VfaIfTmg :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
是
否
是
否
是
否
是
否
是
否
需要排序
需要稳定性?
数据在内存中?
数据量小?
归并排序或 TimSort
外部归并排序(分块+归并)
插入排序(快排的cutoff)
大量重复?
三路快排
数据在链表上?
归并排序(链表天然适配)
快速排序(随机化+Hoare)
4.3 面试标准答法
“归并排序和快速排序的区别?”
归并排序是"先拆后合"——拆分 O(1),合并 O(n),需要 O(n) 辅助空间,但稳定且最坏 O(n log n)。快速排序是"先分后治"——分区 O(n),无需合并,原地排序 O(log n) 栈空间,但不稳定且最坏 O(n²)。工程中,需要稳定性选归并(如对象排序),追求速度选快排(如基本类型排序),两者都通过随机化和优化避免退化。
五、LeetCode 实战
🟢 入门题
| 148 | 排序链表 | 链表归并排序 | 快慢指针找中点 + 断开 + 合并 |
| 912 | 排序数组 | 手写快排/归并 | 注意边界和优化 |
| 75 | 颜色分类 | 三路分区 | 只有0/1/2,一次扫描搞定 |
🟡 进阶题
| 215 | 数组中第K个最大元素 | 快速选择 | partition后只递归一侧,期望O(n) |
| 493 | 翻转对 | 归并排序变体 | merge时统计跨越两半的翻转对 |
| 56 | 合并区间 | 排序+贪心 | 按左端点排序后线性扫描 |
| 23 | 合并K个升序链表 | 归并思想 | 分治合并或小顶堆 |
🔴 困难题
| 327 | 区间和的个数 | 归并+前缀和 | 转化为前缀和的计数问题 |
| 315 | 计算右侧小于当前元素的个数 | 归并排序变体 | merge时统计右侧更小元素 |
5.1 经典题详解:快速选择(LeetCode 215)
public int findKthLargest(int[] nums, int k) {
// 第K大 = 第 (n-k) 小(升序位置)
return quickSelect(nums, 0, nums.length – 1, nums.length – k);
}
private int quickSelect(int[] arr, int left, int right, int k) {
if (left == right) return arr[left];
int pivotIdx = partitionLomuto(arr, left, right);
if (k == pivotIdx) {
return arr[k];
} else if (k < pivotIdx) {
return quickSelect(arr, left, pivotIdx – 1, k);
} else {
return quickSelect(arr, pivotIdx + 1, right, k);
}
}
复杂度分析:
| 最好 | O(n) | 每次分区恰好命中 |
| 平均 | O(n) | n + n/2 + n/4 + … ≈ 2n |
| 最坏 | O(n²) | 每次只排除一个元素 |
面试加分:快速选择 + 随机化 pivot = 期望 O(n),这是求 TopK 最优的比较算法。
5.2 经典题详解:逆序对计数
核心思想:在归并排序的 merge 阶段,当右半元素先于左半元素被取出时,说明左半剩余元素都比右半当前元素大,产生逆序对。
private static int mergeAndCount(int[] arr, int left, int mid, int right) {
int count = 0;
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
temp[k] = arr[j++];
} else if (j > right) {
temp[k] = arr[i++];
} else if (arr[i] <= arr[j]) {
temp[k] = arr[i++];
} else {
// arr[i] > arr[j]: 左半剩余元素都 > arr[j]
count += (mid – i + 1); // 关键:统计逆序对
temp[k] = arr[j++];
}
}
for (int k = left; k <= right; k++) {
arr[k] = temp[k];
}
return count;
}
#mermaid-svg-FTg3CQbkUKUbXFhL{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-FTg3CQbkUKUbXFhL .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-FTg3CQbkUKUbXFhL .error-icon{fill:#552222;}#mermaid-svg-FTg3CQbkUKUbXFhL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-FTg3CQbkUKUbXFhL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-FTg3CQbkUKUbXFhL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-FTg3CQbkUKUbXFhL .marker.cross{stroke:#333333;}#mermaid-svg-FTg3CQbkUKUbXFhL svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-FTg3CQbkUKUbXFhL p{margin:0;}#mermaid-svg-FTg3CQbkUKUbXFhL .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster-label text{fill:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster-label span{color:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster-label span p{background-color:transparent;}#mermaid-svg-FTg3CQbkUKUbXFhL .label text,#mermaid-svg-FTg3CQbkUKUbXFhL span{fill:#333;color:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL .node rect,#mermaid-svg-FTg3CQbkUKUbXFhL .node circle,#mermaid-svg-FTg3CQbkUKUbXFhL .node ellipse,#mermaid-svg-FTg3CQbkUKUbXFhL .node polygon,#mermaid-svg-FTg3CQbkUKUbXFhL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-FTg3CQbkUKUbXFhL .rough-node .label text,#mermaid-svg-FTg3CQbkUKUbXFhL .node .label text,#mermaid-svg-FTg3CQbkUKUbXFhL .image-shape .label,#mermaid-svg-FTg3CQbkUKUbXFhL .icon-shape .label{text-anchor:middle;}#mermaid-svg-FTg3CQbkUKUbXFhL .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-FTg3CQbkUKUbXFhL .rough-node .label,#mermaid-svg-FTg3CQbkUKUbXFhL .node .label,#mermaid-svg-FTg3CQbkUKUbXFhL .image-shape .label,#mermaid-svg-FTg3CQbkUKUbXFhL .icon-shape .label{text-align:center;}#mermaid-svg-FTg3CQbkUKUbXFhL .node.clickable{cursor:pointer;}#mermaid-svg-FTg3CQbkUKUbXFhL .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-FTg3CQbkUKUbXFhL .arrowheadPath{fill:#333333;}#mermaid-svg-FTg3CQbkUKUbXFhL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-FTg3CQbkUKUbXFhL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-FTg3CQbkUKUbXFhL .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-FTg3CQbkUKUbXFhL .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-FTg3CQbkUKUbXFhL .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-FTg3CQbkUKUbXFhL .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster text{fill:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL .cluster span{color:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL 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-FTg3CQbkUKUbXFhL .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-FTg3CQbkUKUbXFhL rect.text{fill:none;stroke-width:0;}#mermaid-svg-FTg3CQbkUKUbXFhL .icon-shape,#mermaid-svg-FTg3CQbkUKUbXFhL .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-FTg3CQbkUKUbXFhL .icon-shape p,#mermaid-svg-FTg3CQbkUKUbXFhL .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-FTg3CQbkUKUbXFhL .icon-shape .label rect,#mermaid-svg-FTg3CQbkUKUbXFhL .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-FTg3CQbkUKUbXFhL .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-FTg3CQbkUKUbXFhL .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-FTg3CQbkUKUbXFhL :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
merge时统计逆序对
左半: [5, 7, 8]
5>1 → 3个逆序对5>3 → 3个逆序对7>6 → 2个逆序对8>6 → 1个逆序对
右半: [1, 3, 6]
共 9 个逆序对
六、面试速查表
| 归并排序的时间/空间复杂度? | O(n log n) / O(n) |
| 快速排序的最好/平均/最坏? | O(n log n) / O(n log n) / O(n²) |
| 归并排序为什么稳定? | merge时相等元素取左半,保持原序 |
| 快排为什么不稳定? | 跨距交换可能改变相等元素顺序 |
| 快排怎么避免O(n²)? | 随机化pivot + 三路分区 |
| Lomuto vs Hoare? | Lomuto单指针易懂,Hoare双指针快3倍 |
| 三路分区解决什么问题? | 大量重复元素,全相同O(n) |
| 为什么Java对基本类型用快排? | 不需要稳定性,快排Cache更友好 |
| 为什么Java对对象用归并? | 对象排序需要稳定性 |
| 快速选择的时间复杂度? | 期望O(n),最坏O(n²) |
| 归并排序适合链表的原因? | 不需要随机访问,合并O(1)空间 |
| 逆序对怎么求? | 归并排序merge时统计 |
七、总结全景图
#mermaid-svg-HEHXvX2sVH05iROk{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-HEHXvX2sVH05iROk .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-HEHXvX2sVH05iROk .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-HEHXvX2sVH05iROk .error-icon{fill:#552222;}#mermaid-svg-HEHXvX2sVH05iROk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-HEHXvX2sVH05iROk .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-HEHXvX2sVH05iROk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-HEHXvX2sVH05iROk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-HEHXvX2sVH05iROk .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-HEHXvX2sVH05iROk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-HEHXvX2sVH05iROk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-HEHXvX2sVH05iROk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-HEHXvX2sVH05iROk .marker.cross{stroke:#333333;}#mermaid-svg-HEHXvX2sVH05iROk svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-HEHXvX2sVH05iROk p{margin:0;}#mermaid-svg-HEHXvX2sVH05iROk .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-HEHXvX2sVH05iROk .cluster-label text{fill:#333;}#mermaid-svg-HEHXvX2sVH05iROk .cluster-label span{color:#333;}#mermaid-svg-HEHXvX2sVH05iROk .cluster-label span p{background-color:transparent;}#mermaid-svg-HEHXvX2sVH05iROk .label text,#mermaid-svg-HEHXvX2sVH05iROk span{fill:#333;color:#333;}#mermaid-svg-HEHXvX2sVH05iROk .node rect,#mermaid-svg-HEHXvX2sVH05iROk .node circle,#mermaid-svg-HEHXvX2sVH05iROk .node ellipse,#mermaid-svg-HEHXvX2sVH05iROk .node polygon,#mermaid-svg-HEHXvX2sVH05iROk .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-HEHXvX2sVH05iROk .rough-node .label text,#mermaid-svg-HEHXvX2sVH05iROk .node .label text,#mermaid-svg-HEHXvX2sVH05iROk .image-shape .label,#mermaid-svg-HEHXvX2sVH05iROk .icon-shape .label{text-anchor:middle;}#mermaid-svg-HEHXvX2sVH05iROk .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-HEHXvX2sVH05iROk .rough-node .label,#mermaid-svg-HEHXvX2sVH05iROk .node .label,#mermaid-svg-HEHXvX2sVH05iROk .image-shape .label,#mermaid-svg-HEHXvX2sVH05iROk .icon-shape .label{text-align:center;}#mermaid-svg-HEHXvX2sVH05iROk .node.clickable{cursor:pointer;}#mermaid-svg-HEHXvX2sVH05iROk .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-HEHXvX2sVH05iROk .arrowheadPath{fill:#333333;}#mermaid-svg-HEHXvX2sVH05iROk .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-HEHXvX2sVH05iROk .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-HEHXvX2sVH05iROk .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-HEHXvX2sVH05iROk .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-HEHXvX2sVH05iROk .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-HEHXvX2sVH05iROk .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-HEHXvX2sVH05iROk .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-HEHXvX2sVH05iROk .cluster text{fill:#333;}#mermaid-svg-HEHXvX2sVH05iROk .cluster span{color:#333;}#mermaid-svg-HEHXvX2sVH05iROk 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-HEHXvX2sVH05iROk .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-HEHXvX2sVH05iROk rect.text{fill:none;stroke-width:0;}#mermaid-svg-HEHXvX2sVH05iROk .icon-shape,#mermaid-svg-HEHXvX2sVH05iROk .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-HEHXvX2sVH05iROk .icon-shape p,#mermaid-svg-HEHXvX2sVH05iROk .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-HEHXvX2sVH05iROk .icon-shape .label rect,#mermaid-svg-HEHXvX2sVH05iROk .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-HEHXvX2sVH05iROk .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-HEHXvX2sVH05iROk .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-HEHXvX2sVH05iROk :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}
O(n log n)排序
归并排序
快速排序
策略: 先拆后合
拆: O(1)取中点
合: O(n)双指针归并
稳定 ✅ / O(n)空间
链表天然适配
应用: 对象排序/外部排序/逆序对
策略: 先分后治
分: O(n)选基准分区
治: 无需合并
不稳定 ❌ / O(log n)空间
优化: 随机化+三路+cutoff+Hoare+尾递归
应用: 基本类型排序/快速选择/颜色分类
选择指南
需稳定 → 归并
需原地 → 快排
链表 → 归并
大量重复 → 三路快排
外部排序 → 归并
一句话带走:归并排序"先拆后合"(稳定+O(n)空间),快速排序"先分后治"(不稳定+原地)。归并的难点在 merge,快排的难点在 partition。快排五板斧优化:随机化pivot、三路分区、插入cutoff、Hoare分区、尾递归优化。链表排序用归并(O(1)空间),逆序对用归并(merge时统计),TopK用快速选择(期望O(n))。Java 对基本类型用快排(不需要稳定),对对象用归并(需要稳定)。

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

