01先从一个问题出发
先让班级按一个人的身高分两组，再分别整理每组。
一个具体的例子
[4, 2, 5, 3] 以 3 为基准，分区后得到 [2, 3, 5, 4]；3 已在最终位置。
02最直接的办法，为什么慢？
使用相邻交换反复扫描整个数组。
暴力 · O(n²)
每次只能消除局部逆序，可能需要平方级比较。
03一步步，推导出优化思路
1
发现可以复用的信息
先确定某个基准的最终位置，就能把大问题拆成互不干扰的两边。
2
建立可维护的状态
boundary 左侧维护不大于基准的元素，扫描时按需交换。
3
消除重复工作
把基准放到 boundary，再递归排序左右区间。
贯穿算法的不变量
扫描时 a[left:boundary] ≤ pivot，a[boundary:j] > pivot。
04让每一步，都看得见
试着先预测下一步，再点击「下一步」验证。变量、动画与代码会同步变化。
Quick Sort交互演示
STEP 01 / 3335
018
152
227
343
412
560
631
7当前处理已处理 / 已确定未处理
01
从左到右观察数组。橙色表示当前比较，绿色表示已确定的位置。
quick_sort.py参考实现 · 当前第 2 行
正在载入代码编辑器…
动画展示参考实现的执行轨迹。切换语言时，当前操作会定位到对应代码行。
05复杂度，来自具体的工作量
时间复杂度
分区平衡时递归深度 O(log n)，每层 O(n)。本课固定末元素为基准，已排序或全相等输入可退化到 O(n²)；平均复杂度依赖输入分布。
辅助空间
平衡递归栈 O(log n)，最坏 O(n)。教学函数复制输入还需 O(n)；工程中可随机化基准或三路分区。
06看到什么，应该想到它？
这些特征值得停下来想一想：
07这些细节，容易踩坑
01
固定基准可能退化
在逆序、已有序或大量相同值上观察分区不平衡。
02
不稳定
跨位置交换可能颠倒相等元素的次序。
08把想法带进真实题目
先说出模式和适用条件，再开始写代码。
09不用背模板，回答这几个问题
01分区后确定了哪个元素的位置？
02末尾基准遇到有序输入可能怎样？
03普通快速排序稳定吗？
你已经走完了这次推导。
能用自己的话解释复杂度和不变量，再标记为掌握。