1. 概述
高效的排序算法在降低问题复杂度方面起着至关重要的作用。排序算法广泛应用于计算机科学中，用于将数组或列表中的元素按升序或降序排列。
快速排序（Quicksort） 是一种基于 分治策略（Divide-and-Conquer） 的高效排序算法。
在本教程中，我们将详细分析快速排序在最坏情况下的表现及其时间复杂度。
2. 快速排序的最坏情况何时发生？
快速排序的性能高度依赖于 基准值（pivot） 的选择：
✅ 最坏情况一：输入数组已排序，且选取最左元素为 pivot
此时每次划分都会产生两个极不平衡的子数组，一个长度为 1，另一个长度为 N-1。
✅ 最坏情况二：输入数组为逆序，且选取最右元素为 pivot
同样会导致划分极度不平衡。
✅ 最坏情况三：所有元素相同
在这种情况下，无论选择哪个 pivot，都无法将数组有效分割，也会导致最坏性能。
3. 最坏情况时间复杂度分析
我们假设每次划分都产生最不平衡的子数组，如下图所示：
每个框中的数字表示当前数组或子数组的大小。
3.1 分析思路
假设输入数组大小为 N：
- 第一次 partition 需要 N 次比较
- 每次递归调用 partition，数组大小递减 1
- 总操作次数为：
N + (N - 1) + (N - 2) + ... + 2 = [N(N + 1)/2] - 1 = O(N²)
3.2 使用递推公式分析
设 T(N) 表示排序 N 个元素的最坏时间复杂度：
T(N) = N + T(N - 1)
T(1) = 0
展开递推式可得：
T(N) = N + (N - 1) + (N - 2) + ... + 2 = O(N²)
⚠️ 这说明在最坏情况下，快速排序的性能会退化为冒泡排序级别。
4. 如何避免最坏情况？
为了避免最坏情况，我们应谨慎选择 pivot 元素：
✅ 选择中间位置元素作为 pivot
这样可以尽可能均匀地划分数组。
✅ 随机选择 pivot
这种方式称为 随机化快速排序（Randomized Quicksort），能有效避免极端情况。
✅ 三数取中法（Median of Three）
取数组首、中、尾三个元素的中位数作为 pivot，进一步提升划分的平衡性。
5. 快速排序的优缺点
✅ 优点
- 平均时间复杂度为 **O(N log N)**，与归并排序相当
- 原地排序，空间复杂度为 O(1)
- 实现简单，性能优秀，尤其适合大规模数据
❌ 缺点
- 最坏情况时间复杂度为 **O(N²)**，对 pivot 选择敏感
- 不是稳定排序算法（相同元素的相对顺序可能被打乱）
6. 实现参考
如需查看快速排序的 Java 实现，可参考我们的文章：Java 快速排序实现
7. 总结
本文我们分析了快速排序在以下几种情况下的最坏表现：
- 输入数组已排序 + 选择最左元素为 pivot
- 输入数组为逆序 + 选择最右元素为 pivot
- 所有元素相同
在这些情况下，快速排序的时间复杂度会退化为 **O(N²)**。但通过合理选择 pivot（如三数取中法或随机选择），可以大大降低最坏情况发生的概率，从而提升整体性能。
快速排序是一个在实践中非常高效的排序算法，但在使用时一定要注意 pivot 的选择策略，避免踩坑。