快速排序（Quick Sort）详解：从原理到实例
快速排序是一种基于分治法的高效排序算法，平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。下面以经典的“左右指针法”为例，详细拆解它的完整工作流程。
前置知识：分治与基准数
- 分治法：将大问题分解为小问题，解决小问题后合并结果。
- 基准数（Pivot）：每一轮排序选一个元素作为“标杆”，通过交换让比它小的数到左边，比它大的数到右边，最终基准数会到达它在有序数组中的正确位置。
快速排序的两大步骤
- 分区（Partition）：选一个基准数，通过左右指针扫描和交换，把数组分成“左小右大”两部分，基准数归位。
- 递归排序：对基准数左边和右边的子数组重复“分区”操作，直到子数组长度为1或0。
分区操作的详细流程（左右指针法）
以数组 [5, 3, 8, 4, 2, 7, 1, 6] 为例，选第一个元素 5 作为基准数，演示分区过程：
| 步骤 | 操作 | 数组状态 | 说明 |
|---|---|---|---|
| 初始 | 左指针 left=0（指向5），右指针 right=7（指向6），基准数 pivot=5 |
[5, 3, 8, 4, 2, 7, 1, 6] |
准备开始分区 |
| 1 | 右指针从右往左找小于5的元素：right=6（指向1） |
[5, 3, 8, 4, 2, 7, 1, 6] |
1 < 5，停止左移 |
| 2 | 左指针从左往右找大于5的元素：left=2（指向8） |
[5, 3, 8, 4, 2, 7, 1, 6] |
8 > 5，停止右移 |
| 3 | 交换 left=2 和 right=6 的元素 |
[5, 3, 1, 4, 2, 7, 8, 6] |
把小的1换到左边，大的8换到右边 |
| 4 | 右指针继续左移找小于5的元素：right=4（指向2） |
[5, 3, 1, 4, 2, 7, 8, 6] |
2 < 5，停止左移 |
| 5 | 左指针继续右移找大于5的元素：left=4（指向2） |
[5, 3, 1, 4, 2, 7, 8, 6] |
左右指针相遇，停止右移 |
| 6 | 交换基准数（索引0）和重合位置（索引4）的元素 | [2, 3, 1, 4, 5, 7, 8, 6] |
基准数5到达最终位置，左边都是<5的数，右边都是>5的数 |
递归排序子数组
分区后，数组被分成两部分：
- 左子数组：
[2, 3, 1, 4]（都<5） - 右子数组：
[7, 8, 6]（都>5）
对这两个子数组重复“分区+递归”操作，直到所有子数组长度为1或0。
以左子数组 [2, 3, 1, 4] 为例：
- 选基准数
2，分区后得到[1, 2, 3, 4]（2归位，左边[1]，右边[3,4]） - 对
[3,4]分区，选基准数3，得到[3,4]（3归位，右边[4]）
最终所有元素归位，排序完成。
快速排序的特点
- 优点：平均时间复杂度 O(n log n)，原地排序（空间复杂度 O(log n)，递归栈开销），实际运行速度快。
- 缺点：最坏时间复杂度 O(n²)（如数组已有序时，每次选的基准数都是最大/最小值），可通过“随机选基准数”或“三数取中”优化。
代码实现（Python）
- 左右指针法（原地分区）
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low >= high:
return arr
pivot = arr[low]
left, right = low, high
while left < right:
while left < right and arr[right] >= pivot:
right -= 1
while left < right and arr[left] <= pivot:
left += 1
arr[left], arr[right] = arr[right], arr[left]
arr[low], arr[right] = arr[right], arr[low]
quick_sort(arr, low, right - 1)
quick_sort(arr, right + 1, high)
return arr
# 测试
arr = [5, 3, 8, 4, 2, 7, 1, 6]
print(quick_sort(arr))
- 函数式分区法，遍历了两次 arr[1:]
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] # 选第一个元素为基准数
left = [x for x in arr[1:] if x <= pivot] # 小于等于基准数的放左边
right = [x for x in arr[1:] if x > pivot] # 大于基准数的放右边
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试
arr = [5, 3, 8, 4, 2, 7, 1, 6]
print(quick_sort(arr)) # 输出 [1, 2, 3, 4, 5, 6, 7, 8]