快速排序算法时间复杂度递归公式全解析：从入门到精通
在计算机科学领域，快速排序算法（Quick Sort）无疑是最著名且应用最广泛的排序算法之一。由 C. A. R. Hoare 在 1960 年提出，它基于分治法（Divide and Conquer）策略。尽管在最坏情况下其性能退化为 O(n²)，但在大多数实际应用场景中，其平均时间复杂度为 O(n log n)，且常数因子极小，使其成为许多标准库排序函数的首选。
本文旨在深入探讨快速排序算法时间复杂度递归公式的推导过程，解析其最好、最坏及平均情况下的数学逻辑，并提供直观的代码示例与优化方案，帮助开发者彻底理解这一核心算法。
⚡ 核心优势
原地排序（In-place），无需额外大量存储空间；缓存命中率高，实际运行速度极快。
⚙️ 基本原理
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。
📊 适用场景
适用于大规模数据排序，尤其是对随机分布的数据集效果最佳。不适用于对稳定性有严格要求的场景。
快速排序算法时间复杂度递归公式深度推导
理解快速排序算法时间复杂度递归公式是掌握该算法的关键。快速排序的核心操作是“划分”（Partition）。假设对 n 个元素的数组进行排序，划分操作本身需要遍历整个数组，耗时 O(n)。如果划分后，基准元素将数组分成了大小为 k 和 n-k-1 的两个子数组，则递归公式可表示为：
T(n) = T(k) + T(n - k - 1) + O(n)
1. 最好情况：O(n log n)
当每次划分都非常均匀，即基准元素恰好将数组分成两个大小相等的子数组时（k ≈ n/2），递归公式变为：
T(n) = 2T(n/2) + O(n)
根据主定理（Master Theorem）或递归树法，该公式的解为 T(n) = O(n log n)。这是理想状态，类似于二分查找的效率。
2. 最坏情况：O(n²)
当每次划分都极不均匀，例如数组已经有序，且我们总是选择第一个元素作为基准（pivot），此时一个子数组为空（k=0），另一个子数组包含 n-1 个元素。递归公式变为：
T(n) = T(n - 1) + O(n)
展开后为 T(n) = O(n) + O(n-1) + ... + O(1) = O(n(n+1)/2)，即 T(n) = O(n²)。这与冒泡排序的效率相当，是我们极力避免的情况。
3. 平均情况：O(n log n)
在随机排列的数组中，假设划分比例是常数 α:β (0 < α, β < 1, α + β = 1)，递归公式为：
T(n) = T(αn) + T(βn) + O(n)
通过数学推导（通常使用代入法），可以证明无论 α 和 β 取何值（只要它们是常数），其解仍然是 T(n) = O(n log n)。这解释了为什么快速排序在实际应用中表现优异。
| 情况 | 划分状态 | 递归公式 | 时间复杂度 |
|---|---|---|---|
| 最好 | 均匀划分 (n/2 : n/2) | T(n) = 2T(n/2) + n | O(n log n) |
| 平均 | 随机划分 | T(n) = T(αn) + T(βn) + n | O(n log n) |
| 最坏 | 极不均匀 (0 : n-1) | T(n) = T(n-1) + n | O(n²) |
快速排序代码实现与示例
为了更直观地理解快速排序算法时间复杂度递归公式在实际代码中的体现，以下是 Java 和 Python 的标准实现。注意，这里的实现采用了基础的“选择第一个元素为基准”的策略，因此在有序数组上会触发最坏情况。
public class QuickSort {
public static void sort(int[] arr, int low, int high) {
if (low < high) {
// 获取划分位置
int pivotIndex = partition(arr, low, high);
// 递归排序左子数组
sort(arr, low, pivotIndex - 1);
// 递归排序右子数组
sort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准
int i = low + 1;
int j = high;
while (true) {
while (i <= j && arr[i] <= pivot) i++;
while (i <= j && arr[j] >= pivot) j--;
if (i > j) break;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 将基准元素放到正确位置
arr[low] = arr[j];
arr[j] = pivot;
return j;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
sort(arr, 0, arr.length - 1);
System.out.println("排序后: " + Arrays.toString(arr));
}
}
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
# 选择基准元素（这里选择中间元素以避免最坏情况）
pivot = arr[len(arr) // 2]
# 三部分：小于、等于、大于
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
# 递归排序并合并
return quick_sort(left) + middle + quick_sort(right)
示例使用
data = [10, 7, 8, 9, 1, 5]
sorted_data = quick_sort(data)
print("排序后:", sorted_data)
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
function partition(arr, low, high) {
const pivot = arr[high]; // 选择最后一个元素作为基准
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
// 示例使用
const data = [10, 7, 8, 9, 1, 5];
console.log("排序后:", quickSort(data));
快速排序优化策略
为了避免快速排序算法时间复杂度递归公式中的最坏情况 O(n²)，实际工程中通常采用以下优化策略：
在选取基准元素时，不固定选择第一个或最后一个，而是选择左端、右端和中间三个元素的中位数作为基准。这能有效避免在已排序或接近排序数组上的最坏表现。
当子数组规模较小时（如 n <= 10），递归调用的开销可能超过排序本身。此时切换到插入排序，因为插入排序在小规模数据上常数因子更小，效率更高。
在递归调用时，先对较小的子数组进行递归，然后对较大的子数组使用循环或尾递归优化，以将递归栈深度限制在 O(log n)，防止栈溢出。
将数组划分为小于、等于、大于基准的三部分。这在处理大量重复元素时能显著减少递归深度，将时间复杂度从 O(n log n) 进一步优化到接近 O(n)（当有大量重复值时）。
与其他排序算法的深度对比
在面试和实际开发中，经常需要对比不同排序算法的优劣。以下是快速排序与归并排序、堆排序的详细对比：
| 特性 | 快速排序 (Quick Sort) | 归并排序 (Merge Sort) | 堆排序 (Heap Sort) |
|---|---|---|---|
| 最好时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n²) | O(n log n) | O(n log n) |
| 空间复杂度 | O(log n) ~ O(n) | O(n) | O(1) |
| 稳定性 | 不稳定 | 稳定 | 不稳定 |
| 缓存友好性 | 高 (局部性好) | 低 (需额外数组) | 低 (跳跃访问) |
| 适用场景 | 通用排序，内存受限 | 链表排序，需稳定排序 | Top K 问题，内存极受限 |
从表中可以看出，虽然快速排序在最坏情况下表现不佳，但其优异的空间局部性和较小的常数因子，使其在大多数通用场景下优于归并排序和堆排序。
网友们还关心：快速排序常见问题解答
基于搜索引擎的热搜数据，我们整理了开发者在理解快速排序算法时间复杂度递归公式时最常遇到的困惑：
尽管两者的平均时间复杂度都是 O(n log n)，但快速排序的常数因子更小。原因包括：1) 快速排序是原地排序，不需要额外的 O(n) 空间，减少了内存分配开销；2) 快速排序的内存访问模式具有良好的局部性（Cache Locality），更适合现代 CPU 的缓存机制；3) 归并排序在合并阶段需要额外的数组拷贝操作。
可以通过以下几种方式避免：1) 随机选择基准元素（Randomized Quick Sort），使得最坏情况出现的概率极低；2) 使用“三数取中法”选择基准；3) 切换到三路划分（Three-way Partitioning），处理大量重复元素；4) 结合插入排序处理小规模子数组。
标准的快速排序是不稳定的。因为在划分过程中，相等元素的相对位置可能会发生改变。如果需要稳定排序，可以考虑使用归并排序，或者对快速排序进行改造（如使用三路划分并记录原始索引，但这会增加空间复杂度）。
空间复杂度主要来源于递归调用栈的深度。在最好和平均情况下，递归树的深度为 O(log n)，因此栈空间为 O(log n)。在最坏情况下，递归树退化为链表，深度为 O(n)，栈空间为 O(n)。通过尾递归优化，可以将最坏情况的空间复杂度也控制在 O(log n)。
不太适合。虽然可以对链表实现快速排序，但由于链表不支持随机访问，划分操作（Partition）的效率会低于数组。相比之下，归并排序更适合链表排序，因为它只需要顺序访问，且可以原地合并（虽然标准实现需要 O(log n) 栈空间）。