异常教程
Python 快速排序（一文讲透）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观
在编程世界中，排序算法如同整理房间的魔法工具，帮助开发者将混乱的数据变得井然有序。Python 快速排序作为经典排序算法之一，以其高效的性能和直观的逻辑，成为开发者必须掌握的核心技能。无论是处理海量数据、优化程序效率，还是理解算法设计的思想，快速排序都能提供极具启发性的视角。本文将从零开始，通过案例、代码和直观的比喻，带您一步步揭开快速排序的奥秘。
一、快速排序的基本概念与核心思想
1.1 什么是快速排序？
快速排序（QuickSort）是一种基于分治法（Divide and Conquer）的高效排序算法。它的核心思想是通过“分而治之”将一个大问题分解为多个小问题，最终快速解决。
形象比喻：
想象你要整理一个杂乱的书架，快速排序就像这样操作：
- 选基准：先挑一本中间的书作为“基准点”。
- 分左右：把比它薄的书放在左边，比它厚的放在右边。
- 递归整理：对左右两边的小书架重复上述步骤，直到每摞书都只有一本。
1.2 快速排序的特性
- 时间复杂度：平均情况为 O(n log n)，最坏情况为 O(n²)（当数据已排序或逆序时）。
- 空间复杂度：平均 O(log n)（递归栈空间），最坏 O(n)。
- 稳定性：不稳定（相同值的元素可能因分区顺序不同而改变相对位置）。
二、快速排序的实现步骤详解
2.1 步骤分解
快速排序的实现可以分为以下三个关键步骤：
步骤 1：选择基准值（Pivot）
从数组中选择一个元素作为基准值。常见的选择方式包括：
- 取第一个元素；
- 取最后一个元素；
- 取中间元素；
- 随机选择（推荐，以减少最坏情况的概率）。
步骤 2：分区操作（Partition）
将数组分为两部分：
- 左区：所有元素 ≤ 基准值；
- 右区：所有元素 ≥ 基准值。
基准值最终会被放置到正确的位置，使其左边的元素都小于它，右边的元素都大于它。
步骤 3：递归排序子数组
对左区和右区重复上述步骤，直到子数组长度为 1 或 0。
三、Python 实现快速排序的代码示例
3.1 基础版实现
以下是一个简单的快速排序函数实现：
def quick_sort(arr):
if len(arr) <= 1:
return arr
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)
代码解释：
- 当数组长度 ≤ 1 时，直接返回原数组（递归终止条件）。
- 使用列表推导式将元素分为左区（小于基准值）、中间区（等于基准值）、右区（大于基准值）。
- 递归排序左区和右区，最终合并结果。
测试案例：
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
3.2 原地排序优化
基础版实现虽然直观，但每次递归都会生成新列表，导致额外内存开销。通过原地排序可以优化空间复杂度：
def partition(arr, low, high):
pivot = arr[high] # 选择最后一个元素作为基准值
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # 交换元素
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
def quick_sort_inplace(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pi = partition(arr, low, high)
quick_sort_inplace(arr, low, pi-1)
quick_sort_inplace(arr, pi+1, high)
return arr
关键改进点：
- 分区函数：通过交换元素实现原地分区，避免创建新列表。
- 基准值选择：这里选择最后一个元素作为基准值，但也可以随机化（如
random.choice）。
测试案例：
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort_inplace(arr))
四、快速排序的优化与进阶
4.1 随机选择基准值
为了避免最坏情况（如输入数组已排序），可随机选择基准值：
import random
def partition_optimized(arr, low, high):
# 随机选择基准值并交换到末尾
pivot_index = random.randint(low, high)
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
pivot = arr[high]
# 后续步骤与原分区函数相同...
4.2 尾递归优化
通过将最后的递归调用改为迭代形式，减少栈溢出风险：
def quick_sort_tail_recursive(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
stack = [(low, high)]
while stack:
low, high = stack.pop()
if low >= high:
continue
pi = partition(arr, low, high)
stack.append((pi+1, high)) # 先保留右区，后处理左区（栈的特性）
stack.append((low, pi-1))
return arr
五、快速排序的性能分析与适用场景
5.1 时间复杂度对比
以下是几种常见排序算法的时间复杂度对比：
| 算法名称 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
结论：快速排序在平均情况下表现优异，但需注意最坏情况的规避，适合处理大规模无序数据。
5.2 实际应用案例
场景：电商平台需对商品销量进行实时排序。
sales = [1200, 850, 3400, 150, 4500, 2200]
sorted_sales = quick_sort(sales)
print("排序后的销量：", sorted_sales)
六、常见问题与调试技巧
6.1 快速排序的递归深度问题
当输入数据接近有序时，递归深度可能达到 O(n)，导致栈溢出。可以通过以下方式解决：
- 三数取中法：选择数组首、中、尾三个元素的中位数作为基准值；
- 改为迭代实现：如前文提到的尾递归优化。
6.2 如何调试快速排序代码？
- 打印中间结果：在分区函数中添加
print语句，观察数组变化； - 单元测试：编写测试用例覆盖边界情况（如空数组、单元素数组、全相同元素）。
结论
Python 快速排序凭借其简洁的逻辑和高效的性能，成为开发者工具箱中的重要一员。通过本文的逐步讲解，您不仅掌握了快速排序的实现原理，还学会了如何通过优化技巧提升其鲁棒性。无论是处理日常的数据排序任务，还是为算法面试做准备，快速排序都是值得深入理解的算法。
建议读者通过以下实践进一步巩固：
- 尝试修改基准值选择策略，观察性能差异；
- 将快速排序与归并排序、堆排序进行性能对比；
- 在实际项目中替换原有排序逻辑，体验效率提升。
通过持续练习，您将真正掌握这一经典算法的力量。