快速排序 图解题解
这道题到底在问什么
- 输入
- nums = [5,2,7,3,1,6,4]
- 输出
- [1,2,3,4,5,6,7]
最优解：一步一步想明白
- 3记住三个角色：pivot 基准(橙)、边界 i(小区右端)、扫描指针 j。小于基准就「换进小区」，否则跳过。
- 4本轮处理下标 0~6 这一段。基准 pivot = 最右的 4（橙色）。边界 i 先停在 -1（小区还空着），指针 j 从下标 0 开始往右扫。
- 5指针 j 走到下标 0，值是 5。和基准 4 比一比：5 不小于 4，留在原地、j 直接跳过。
- 6指针 j 走到下标 1，值是 2。和基准 4 比一比：2 小于 4，要换进左边小区。
- 72 小于基准：边界 i 前进到 0，把下标 0 和下标 1 的数交换，2 进了左边小区，原来 0 处的数被换到了 1。
- 8指针 j 走到下标 2，值是 7。和基准 4 比一比：7 不小于 4，留在原地、j 直接跳过。
- 9指针 j 走到下标 3，值是 3。和基准 4 比一比：3 小于 4，要换进左边小区。
- 103 小于基准：边界 i 前进到 1，把下标 1 和下标 3 的数交换，3 进了左边小区，原来 1 处的数被换到了 3。
- 11指针 j 走到下标 4，值是 1。和基准 4 比一比：1 小于 4，要换进左边小区。
- 121 小于基准：边界 i 前进到 2，把下标 2 和下标 4 的数交换，1 进了左边小区，原来 2 处的数被换到了 4。
- 13指针 j 走到下标 5，值是 6。和基准 4 比一比：6 不小于 4，留在原地、j 直接跳过。
- 14扫描结束。把基准 4 换到边界后一格(下标 3)：原来 3 处的数被换到了最右。现在 4 左边全比它小、右边全比它大。
- 15基准 4 标绿——它已经在最终位置，永远不再动。接下来分别对它左边 [0~2] 和右边 [4~6] 两段重复同样的分区。
- 16本轮处理下标 0~2 这一段。基准 pivot = 最右的 1（橙色）。边界 i 先停在 -1（小区还空着），指针 j 从下标 0 开始往右扫。
- 17指针 j 走到下标 0，值是 2。和基准 1 比一比：2 不小于 1，留在原地、j 直接跳过。
- 18指针 j 走到下标 1，值是 3。和基准 1 比一比：3 不小于 1，留在原地、j 直接跳过。
- 19扫描结束。把基准 1 换到边界后一格(下标 0)：原来 0 处的数被换到了最右。现在 1 左边全比它小、右边全比它大。
- 20基准 1 标绿——它已经在最终位置，永远不再动。接下来分别对它左边 [0~-1] 和右边 [1~2] 两段重复同样的分区。
- 21本轮处理下标 1~2 这一段。基准 pivot = 最右的 2（橙色）。边界 i 先停在 0（小区还空着），指针 j 从下标 1 开始往右扫。
- 22指针 j 走到下标 1，值是 3。和基准 2 比一比：3 不小于 2，留在原地、j 直接跳过。
- 23扫描结束。把基准 2 换到边界后一格(下标 1)：原来 1 处的数被换到了最右。现在 2 左边全比它小、右边全比它大。
- 24基准 2 标绿——它已经在最终位置，永远不再动。接下来分别对它左边 [1~0] 和右边 [2~2] 两段重复同样的分区。
- 25本轮处理下标 4~6 这一段。基准 pivot = 最右的 5（橙色）。边界 i 先停在 3（小区还空着），指针 j 从下标 4 开始往右扫。
- 26指针 j 走到下标 4，值是 7。和基准 5 比一比：7 不小于 5，留在原地、j 直接跳过。
- 27指针 j 走到下标 5，值是 6。和基准 5 比一比：6 不小于 5，留在原地、j 直接跳过。
- 28扫描结束。把基准 5 换到边界后一格(下标 4)：原来 4 处的数被换到了最右。现在 5 左边全比它小、右边全比它大。
- 29基准 5 标绿——它已经在最终位置，永远不再动。接下来分别对它左边 [4~3] 和右边 [5~6] 两段重复同样的分区。
- 30本轮处理下标 5~6 这一段。基准 pivot = 最右的 7（橙色）。边界 i 先停在 4（小区还空着），指针 j 从下标 5 开始往右扫。
- 31指针 j 走到下标 5，值是 6。和基准 7 比一比：6 小于 7，要换进左边小区。
- 326 小于基准：边界 i 前进到 5，正好是它自己，原地不动。小区右端推进到下标 5。
- 33扫描结束，边界后一格正好就是基准所在的下标 6，基准 7 不用换、已经归位。
- 34基准 7 标绿——它已经在最终位置，永远不再动。接下来分别对它左边 [5~5] 和右边 [7~6] 两段重复同样的分区。
- 35所有基准都归了位，每个数左边都比它小、右边都比它大——数组已经从小到大排好：[1,2,3,4,5,6,7]。
⚠️ 容易写错的地方
✗ 错：分区后忘了把基准换到 i+1
✓ 对：循环结束必做 swap(a[i+1], a[hi])
不归位基准就没落到正确位置，左小右大的不变式不成立，整个排序错乱
✗ 错：递归区间写成 [lo, i+1] 和 [i+1, hi]
✓ 对：基准下标 i+1 已归位，递归只排 [lo, i] 和 [i+2, hi]
把已归位的基准再纳入递归会重复处理、甚至死循环
✗ 错：基准固定取最右，遇到已排序数组
✓ 对：随机基准或三数取中
已排序时固定取端点会让每轮分区只少一个元素，退化成 O(n²)
完整代码（Python / C++ / Java）
Python
def quicksort(a, lo, hi):
if lo >= hi: return # 段内 ≤1 个数，天然有序
piv = a[hi] # 基准取最右
i = lo - 1 # 小区右端
for j in range(lo, hi): # j 扫到基准前一格
if a[j] < piv: # 小于基准：换进小区
i += 1
a[i], a[j] = a[j], a[i]
a[i+1], a[hi] = a[hi], a[i+1] # 基准归位
quicksort(a, lo, i) # 递归排左段
quicksort(a, i+2, hi) # 递归排右段C++
void quicksort(vector<int>& a, int lo, int hi){
if (lo >= hi) return;
int piv = a[hi], i = lo - 1;
for (int j = lo; j < hi; ++j)
if (a[j] < piv) std::swap(a[++i], a[j]);
std::swap(a[i+1], a[hi]);
quicksort(a, lo, i);
quicksort(a, i+2, hi);
}Java
void quicksort(int[] a, int lo, int hi){
if (lo >= hi) return;
int piv = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < piv) { i++; int t=a[i]; a[i]=a[j]; a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
quicksort(a, lo, i);
quicksort(a, i+2, hi);复杂度
时间(平均)
O(n log n)
每层分区把数组分成两半，约 log n 层，每层合计扫 n 个元素
时间(最坏)
O(n²)
基准每次都选到最大或最小(如已排好序)，分区极度失衡退化成 n 层
空间
O(log n)
原地交换不开新数组，额外开销只在递归栈的深度
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 快速排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
快排为什么平均是 O(n log n)，最坏是 O(n²)？+
平均情况下每次分区把数组大致均分，递归树高约 log n，每层扫 n 个元素，合计 O(n log n)。最坏情况(基准每次都是最值，如对已排序数组取端点基准)分区极不平衡，递归深度退化到 n 层，变 O(n²)。
快排是稳定排序吗？+
不是。分区时的交换会改变相等元素的相对顺序，所以快排不稳定。需要稳定就用归并排序。
快排和归并排序怎么选？+
快排原地、常数小、平均更快，是通用首选；但最坏 O(n²) 且不稳定。归并稳定且最坏也是 O(n log n)，但需 O(n) 额外空间。对链表或要稳定时选归并。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 快速排序 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。