快速排序也是分而治之，但分割方式不同于归并排序。它选一个 pivot，把数组就地划成”小于 pivot 的部分”和”大于等于 pivot 的部分”，然后对两部分递归。
Lomuto 分区
我们用最简单的 Lomuto 方案：pivot 选末尾元素，用两个指针 i 和 j 扫描——j 是探针，i 是”已知小于 pivot 的边界”。
复杂度
- 时间：平均 O(n log n)，最坏 O(n²)（已排序输入 + 朴素 pivot 选择）
- 空间：O(log n)（递归栈）
- 稳定：否
试试看
输入一个已排序的数组（如 1, 2, 3, 4, 5, 6）看 Lomuto 分区在最坏情况下的退化——pivot 总是最大元素，几乎每一步都要扫整个剩余段。
在动画里看什么
- 紫色：当前段的 pivot
- 蓝色：正在与 pivot 比较的元素
- 红色：发生交换的两个位置
- 绿色：pivot 已经落到最终位置（这一格永远不会再动）