快速排序的工作原理是什么，其最坏情况是什么？

Question

Accepted Answer

**快速排序** 是一种分治排序算法，它选择一个 **基准值（pivot）**，将元素分为比基准值小和比基准值大的两组，然后递归地对两侧进行排序。平均时间复杂度为 **O(n log n)**，最坏情况为 **O(n²)**。 ## 基本思想 Partitioning 将基准值放在其最终排序位置；左边的所有元素都较小，右边的所有元素都较大。递归地对两侧进行排序。 ## 示例 ```python def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] # pick a pivot left = [x for x in arr if x < pivot] # smaller mid = [x for x in arr if x == pivot] # equal right = [x for x in arr if x > pivot] # larger return quicksort(left) + mid + quicksort(right) quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8] ``` （实践中使用原地分割以节省内存。） ## 复杂度分析 | 情况 | 时间 | 原因 | |------|------|-------| | 最佳/平均 | O(n log n) | 分割均衡 | | 最坏 | O(n²) | 已排序的数组且选择不佳的基准值 | 原地快速排序使用 **O(log n)** 的栈空间。 ## 何时使用 / 注意事项通常在实践中 **最快**，因为具有高 cache 亲和性和低开销，且是原地排序。通过使用 **随机** 或 **三数取中** 的基准值选择，可以避免 **O(n²)** 的最坏情况。它 **不是稳定的**。 ## 为什么这很重要快速排序是许多标准库中的默认排序算法，原因是其优异的平均情况速度和低内存占用。理解为什么基准值选择会导致 **O(n²)** 的最坏情况，传达了一个关键课题：平均情况和最坏情况可能会产生巨大差异。它是面试中的热门话题，正是因为这种细微差别。

情况	时间	原因
最佳/平均	O(n log n)	分割均衡
最坏	O(n²)	已排序的数组且选择不佳的基准值