【算法】快速排序 quicksort

本文系统整理快速排序的核心思想、Lomuto 划分、递归框架、复杂度、随机化策略

快速排序把主要工作放在“分解”阶段。先选择主元并完成数组划分，使主元左侧元素不大于它、右侧元素大于它；随后递归排序左右区间，无需额外合并

1. 问题定义

给定长度为 n 的数组 A[0…n-1]，将其按非递减顺序排列：
$$A[0]\le A[1]\le \cdots \le A[n-1]$$

示例

输入：[5, 2, 8, 1, 9, 3, 7, 4, 6]
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序通常具有很好的实际性能：

• 平均与期望时间复杂度：O(n log n)；
• 原地划分，额外数组空间较少；
• 缓存局部性通常优于归并排序；
• 但固定主元可能导致最坏 O(n²)。

2. 从归并排序到快速排序

归并排序和快速排序都使用分治，但工作重点不同。

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

归并排序

简单分解

递归排序

复杂合并 O(n)

快速排序

复杂划分 O(n)

递归排序

无需合并 O(1)

相关笔记：《归并排序：从两两合并到分治实现》

3. 核心操作：数组划分

3.1 划分目标

从区间 A[p…r] 中选择一个元素 x 作为主元（pivot）。调整元素位置后，返回主元最终下标 q，并满足：

A[p…q-1] <= A[q]
A[q] = x
A[q+1…r] > A[q]

主元一旦被放到 q，它已经处于最终排序位置，之后不再参与递归。

🎯 Partition 并不保证左右区间内部有序；它只保证左边和右边相对于主元的大小关系正确。

3.2 Lomuto 划分方案

最常见的入门实现选择末尾元素 A[r] 作为主元。

• i：小于等于主元区域的右边界；
• j：当前正在检查的元素；
• A[p…i]：已经确认 <= pivot；
• A[i+1…j-1]：已经确认 > pivot；
• A[j…r-1]：尚未检查；
• A[r]：主元。

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

是

否

是

否

pivot = A[r], i = p-1

j 从 p 扫描到 r-1

A[j] <= pivot？

i++，交换 A[i] 与 A[j]

不交换

还有未检查元素？

交换 A[i+1] 与 A[r]

返回 q = i+1

4. 手算一次完整划分

对数组：

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

选择末尾的 4 作为主元。初始 i = -1。

[2, 1, 3] | 4 | [7, 5, 6, 6]
<= 4 主元 > 4

注意：左右两侧仍可能无序，需要继续递归。

5. Partition 的循环不变量

在每次循环开始时，区间满足：

[p …….. i] [i+1 …. j-1] [j …. r-1] [r]
<= pivot > pivot 未检查 pivot

6. 快速排序递归框架

完成一次划分后：

• 主元已经在最终位置；
• 递归排序 A[p…q-1]；
• 递归排序 A[q+1…r]；
• 不需要合并。

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

否

是

QuickSort(A,p,r)

p < r？

返回

q = Partition(A,p,r)

主元 A[q] 已在最终位置

QuickSort(A,p,q-1)

QuickSort(A,q+1,r)

伪代码

QUICK-SORT(A, p, r):
if p < r:
q = PARTITION(A, p, r)
QUICK-SORT(A, p, q – 1)
QUICK-SORT(A, q + 1, r)

7. 基础 C 语言实现

#include <stdio.h>

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int *A, int p, int r) {
int pivot = A[r];
int i = p – 1;

for (int j = p; j < r; j++) {
if (A[j] <= pivot) {
i++;
swap(&A[i], &A[j]);
}
}

swap(&A[i + 1], &A[r]);
return i + 1;
}

void quickSort(int *A, int p, int r) {
if (p >= r) {
return;
}

int q = partition(A, p, r);
quickSort(A, p, q – 1);
quickSort(A, q + 1, r);
}

8. 为什么会出现最坏情况

Partition 本身每次都扫描当前区间，因此代价是 O(n)。但两侧子问题的大小由主元位置决定。

8.1 最好情况：每次接近均分

若主元每次都接近中间：
$$T(n)=2T(n/2)+O(n)=O(n\log n)$$
递归树深度约为 log n，每层总工作量约为 n。

8.2 最坏情况：每次都极不平衡

如果固定选择末尾元素，而输入已经升序：

[1, 2, 3, 4, 5]

每次主元都是当前最大值，只能产生规模为 n-1 和 0 的两个子问题：
$$T(n)=T(n-1)+O(n)$$
展开后：
$$T(n)=O(n+(n-1)+\cdots +1)=O(n^2)$$
递归深度也会达到 O(n)，存在栈溢出风险。

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

规模 n

规模 n-1

规模 n-2

……

规模 1

9. 随机化快速排序

9.1 随机主元的意义

固定选择某个位置作为主元时，可以针对这一规则构造最差输入。随机选取主元后，输入排列无法稳定决定划分结果。

随机化并没有消除最坏 O(n²)；它使最坏情况连续发生的概率很低，从而让期望时间复杂度达到 O(n log n)。

9.2 随机划分代码

#include <stdlib.h>
#include <time.h>

int randomizedPartition(int *A, int p, int r) {
int randomIndex = p + rand() % (r – p + 1);

// 把随机主元交换到末尾，复用普通 partition。
swap(&A[randomIndex], &A[r]);
return partition(A, p, r);
}

void randomizedQuickSort(int *A, int p, int r) {
if (p >= r) {
return;
}

int q = randomizedPartition(A, p, r);
randomizedQuickSort(A, p, q – 1);
randomizedQuickSort(A, q + 1, r);
}

随机种子只需在程序入口设置一次：

srand((unsigned)time(NULL));

不要在每次递归中重复调用 srand。

10. 完整测试程序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int *A, int p, int r) {
int pivot = A[r];
int i = p – 1;

for (int j = p; j < r; j++) {
if (A[j] <= pivot) {
swap(&A[++i], &A[j]);
}
}

swap(&A[i + 1], &A[r]);
return i + 1;
}

int randomizedPartition(int *A, int p, int r) {
int randomIndex = p + rand() % (r – p + 1);
swap(&A[randomIndex], &A[r]);
return partition(A, p, r);
}

void randomizedQuickSort(int *A, int p, int r) {
if (p >= r) {
return;
}

int q = randomizedPartition(A, p, r);
randomizedQuickSort(A, p, q – 1);
randomizedQuickSort(A, q + 1, r);
}

void printArray(const int *A, int n) {
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], i == n – 1 ? '\\n' : ' ');
}
}

int main(void) {
srand((unsigned)time(NULL));

int A[] = {5, 2, 8, 1, 9, 3, 7, 4, 6};
int n = sizeof(A) / sizeof(A[0]);

printf("排序前：");
printArray(A, n);

randomizedQuickSort(A, 0, n – 1);

printf("排序后：");
printArray(A, n);

return 0;
}

预期输出：

排序前：5 2 8 1 9 3 7 4 6
排序后：1 2 3 4 5 6 7 8 9

11. 复杂度与算法性质

12. 重复元素较多时的问题

Lomuto 划分使用 <= pivot 时，大量与主元相等的元素可能集中到同一侧，导致划分不平衡。
例如：

[5, 5, 5, 5, 5, 5]

普通二路快速排序可能退化。此时适合使用三路划分：

小于 pivot | 等于 pivot | 大于 pivot

递归时只处理“小于”和“大于”两部分，中间等于主元的区间已经就位。

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

待划分区间

< pivot

= pivot

> pivot

继续递归

无需递归

继续递归

13. 快速排序与归并排序对比

14. 一页速记

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

选择主元 pivot

Partition 线性扫描

左侧 <= pivot

主元到最终位置

右侧 > pivot

递归排序左侧

递归排序右侧

无需合并

数组有序

固定主元可能退化

随机主元：期望 O(n log n)

**快速排序通过 O(n) 的 Partition 把主元放到最终位置，再递归处理两侧。均衡划分得到 O(n log n)，极端不平衡划分得到 O(n²)；随机主元可以获得 O(n log n) 的期望时间。