Overview
快速排序选择一个基准值，将小元素放左、大元素放右，递归排序。
Analogy
教师让所有人按是否高于基准身高分成两组，再对各组排序。
Step-by-step
- 基础情况: n<=1则返回
- 选基准(末尾/随机/中位数)
- 分为小于/等于/大于三部分
- 递归排序小于和大于部分
Visual
[3,6,8,10,1,2,1] pivot=3
→less=[1,2,1] equal=[3] greater=[6,8,10]
→[1,1,2,3,6,8,10]
Common mistakes
- 不考虑最坏情况(已排序数组取末尾为基准)
- 相等元素都分入less或greater导致不均匀
Practice questions
- 实现随机pivot选择
- 比较Lomuto和Hoare分区