快速排序面试题解析

手写快排及复杂度分析

这题不是只问快排定义，而是要求候选人能现场写出可运行的原地分区递归，并解释为什么平均 O(nlogn)、最坏 O(n²)、递归栈平均 O(logn)。高质量回答要把 partition 不变量、递归边界、重复元素处理和 pivot 优化一起讲清楚。