8.3 冒泡排序、快速排序·综合题讲评

三路快排把数组分为小于、等于、大于枢轴三段，重复键多时避免等值区反复递归。

手工推演与代码

[2,1,2,3,2]以2分区得[1]|[2,2,2]|[3]。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。等值元素仍分散两侧；区间缩减不严格；返回边界含义不清。

迁移训练

全相等n项用二路与三路快排比较递归规模，三路一次结束。