快速排序如何实现？其时间复杂度在什么情况下会下降？

回答思路

1. 清晰描述分区与递归的基本实现
2. 说明平均时间复杂度为O(n log n)
3. 准确指出最坏O(n^2)的触发场景（已排序数组、固定基准）
4. 讨论优化手段如随机化或三数取中