8.3.2 快速排序

快速排序分区使枢轴左侧不大于、右侧不小于，再递归两边。平均nlogn，极端不平衡退化n²；递归空间取决于深度。

手工推演与代码

[4,1,3,2]以4为枢轴，一趟后4落末端；更好的随机枢轴降低持续极端分割概率。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。分区指针越界；递归区间包含枢轴导致死循环；把随机化写成最坏nlogn。

迁移训练

已排序数组总选首元素时递推T(n)=T(n-1)+O(n)，答案O(n²)。