手写快速排序，并说明什么场景下性能最坏及其原因。

回答思路

1. 正确实现快速排序的分区与递归过程
2. 准确指出最坏场景为已有序或近乎有序且固定取首/尾元素
3. 解释最坏时间复杂度为O(n²)及原因
4. 提到优化手段如随机化选基准、三数取中
5. 清楚比较平均复杂度O(n log n)
6. 能联系递归深度与栈空间