欢迎光临
我们一直在努力

【算法专题·第二章】归并排序与快速排序

【排序算法专题·第二章】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] 是有序的。

三步走:

  • Divide:取中点 mid = (left + right) / 2
  • Conquer:递归排序 arr[left..mid] 和 arr[mid+1..right]
  • Combine:将两个有序子数组合并为一个有序数组
  • 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。

    三步走:

  • Choose:选一个基准元素 pivot
  • Partition:将数组分为 ≤ pivot 和 > pivot 两部分
  • Recurse:递归排序左右两部分(无需合并!)
  • 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 对比:

    维度LomutoHoare
    扫描方式 单指针左→右 双指针两端→中间
    交换次数 较多 较少(平均少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 对基本类型用快排(不需要稳定),对对象用归并(需要稳定)。


    赞(0)
    未经允许不得转载:171主机测评 » 【算法专题·第二章】归并排序与快速排序
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址