Menu
CoddyTech
开始学习

快速排序

最后更新

快速排序是一种围绕“基准值”（pivot）进行排序的分治算法。它先选出一个基准元素，然后对数组分区，让所有更小的元素排在它前面、所有更大的元素排在它后面，这样基准值就固定在了最终的有序位置上。接着它对左右两个分区递归处理。这里的可视化使用 Lomuto 分区方案，以最后一个元素作为基准值。点击“播放”，观看分区和基准值归位的过程。

得益于良好的缓存表现和原地分区，快速排序在实际中通常是最快的通用排序算法，平均复杂度为 O(n log n)。它的最坏情况是 O(n²)（例如基准值选得不好时遇到已经有序的数组），三数取中或随机化等好的基准值策略可以避免这种情况。

时间复杂度与空间复杂度

情况复杂度说明
最好情况O(n log n)分区均衡
平均情况O(n log n)随机顺序
最坏情况O(n²)基准值始终导致分区失衡
空间O(log n)递归栈（原地分区）
稳定性不稳定分区时的交换会打乱相等元素的顺序

分步说明

步骤发生了什么
1选择一个基准值（这里取区间的最后一个元素）。
2分区：把所有比基准值小的元素移到它的左边。
3把基准值交换到分界处，它现在已经在最终位置上。
4对左分区递归地进行快速排序。
5对右分区递归地进行快速排序。

实例演示

用 Lomuto 分区方案（以最后一个元素为基准值）对 [5, 2, 4, 1] 排序：

轮次数组操作
开始[5, 2, 4, 1]对整个区间分区；基准值是 1（最后一个元素）。
1[1, 2, 4, 5]没有元素比 1 小，所以把 1 交换到下标 0；基准值 1 已归位。对右侧的 [2, 4, 5] 递归。
2[1, 2, 4, 5]以 5 为基准值对 [2, 4, 5] 分区；2 和 4 都更小，所以 5 留在末尾并归位。对左侧的 [2, 4] 递归。
3[1, 2, 4, 5]以 4 为基准值对 [2, 4] 分区；2 更小，所以 4 原地不动并归位。2 只有一个元素，已经有序。
完成[1, 2, 4, 5]每个基准值都已固定到位，数组排序完成。

什么时候用快速排序

适合使用不适合使用
你需要一种常数因子小、速度快的通用内存排序。你需要有保证的 O(n log n) 最坏情况时间（改用堆排序或归并排序）。
内存紧张：分区是原地进行的，只需 O(log n) 的栈空间。你需要稳定排序，保留相等键的原有顺序。
数据顺序随机或未知，并且你使用随机化或三数取中的基准值。输入已经有序或接近有序，而基准值又是固定的，会触发 O(n²)。
看重缓存局部性，因为快速排序按顺序访问内存。你要对链表排序，这时归并排序不需要快速排序所依赖的随机访问。

Quick Sort 代码

简洁、可运行的 Quick Sort 实现，提供 Python, JavaScript, Java, C++, C, Pseudocode 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。

Quick Sort 的 Python 代码

Python
1def quick_sort(a, low=0, high=None):2    if high is None:3        high = len(a) - 14    if low < high:5        p = partition(a, low, high)6        quick_sort(a, low, p - 1)7        quick_sort(a, p + 1, high)8    return a9
10
11def partition(a, low, high):12    # Lomuto partition: everything < pivot moves left of it13    pivot = a[high]14    i = low15    for j in range(low, high):16        if a[j] < pivot:17            a[i], a[j] = a[j], a[i]18            i += 119    a[i], a[high] = a[high], a[i]20    return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)
在 Python 在线编辑器中运行这段代码

快速排序常见问题

快速排序的时间复杂度是多少？
快速排序的平均复杂度是 O(n log n)，最好情况也是 O(n log n)，但如果分区始终失衡，最坏情况会退化到 O(n²)。随机选取或三数取中的基准值能让最坏情况几乎不可能出现。
快速排序是稳定的吗？

不是。标准的原地分区会交换相距较远的元素，可能改变相等键的相对顺序。稳定的变体确实存在，但会失去快速排序原地排序的优势。

为什么快速排序通常比归并排序快？
快速排序原地分区，缓存局部性极好，也不需要额外的缓冲区，所以常数因子很小。归并排序虽然同样是 O(n log n)，却要付出 O(n) 缓冲区和更多数据移动的代价。
快速排序和归并排序，该用哪个？
如果要在内存中对数组快速地原地排序，选快速排序，它的常数小，通常更胜一筹。如果你需要稳定排序、有保证的 O(n log n) 最坏情况，或者要对链表或内存放不下的外部数据排序，就选归并排序。
为什么快速排序在有序数组上会变成 O(n²)？
如果固定选第一个或最后一个元素作为基准值，已经有序的输入会让每次分区只分出一个元素，递归深度变成 n 层而不是 log n 层。随机选取基准值或使用三数取中可以打破这种模式，恢复 O(n log n) 的表现。
Lomuto 和 Hoare 分区方案有什么区别？

Lomuto 方案用一个下标从左到右扫描，写起来更简单，所以这里的可视化采用了它。Hoare 方案用两个指针从两端向中间移动，交换次数通常更少，实际中更快，但它在分区步骤中不会把基准值放到最终位置上。

相关资源

更多可视化

Coddy 编程语言插图

在 Coddy 掌握算法

开始