快速排序（Quick Sort）是基于分治思想的经典排序算法，其核心思想是通过“基准值”（pivot）将数组分为两部分，递归地对子数组进行排序。它的平均时间复杂度为 (O(n log n))，是实际应用中最快的排序算法之一。以下是逐步讲解实现过程：
一、快速排序的原理
1. 核心思想
快速排序通过以下步骤实现：
- 选择基准值（Pivot）：从数组中选择一个元素作为基准。
- 分区操作（Partition）：将数组分为两部分： 左半部分的所有元素 ≤ 基准值； 右半部分的所有元素 ≥ 基准值。
- 递归排序：对左右两部分递归执行相同操作，直到子数组长度为1或0。
2. 示例演示
以数组 [5, 3, 8, 4, 2] 为例：
- 选择基准值：例如选择最后一个元素 2 作为基准。
- 分区操作：将小于等于 2 的元素移到左边，大于 2 的移到右边：[2, 3, 4, 5, 8] # 分区后基准值位置固定（索引0）
- 递归处理子数组：对左半部分 [2]（已有序）和右半部分 [3,4,5,8] 重复上述步骤。
二、快速排序的实现步骤
1. 递归函数设计
快速排序通常通过递归实现，函数需接收待排序的子数组范围（如起始索引 low 和结束索引 high）。
2. 分区操作的实现
分区的核心是将元素与基准值比较，并交换位置：
- 使用双指针法：一个指针（i）记录“小于等于基准值区域”的边界，另一个指针（j）遍历数组。
- 当发现 nums[j] ≤ pivot 时，将 nums[j] 与 nums[i+1] 交换，i 向右移动一位。
3. 选择基准值
常见的基准值选择方式有：
- 选择第一个元素；
- 选择最后一个元素（如示例）；
- 选择中间元素；
- 随机选择（优化性能，避免最坏情况）。
三、Python代码实现
3.1 基础版本（递归实现）
def quick_sort(arr, low, high):
if low < high:
# 分区操作，返回基准值的最终位置
pivot_index = partition(arr, low, high)
# 递归排序左右子数组
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
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[i], arr[j] = arr[j], arr[i]
# 将基准值放到正确位置
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
# 测试
test_list = [64, 34, 25, 12, 22, 11, 90]
quick_sort(test_list, 0, len(test_list)-1)
print("排序后：", test_list) # 输出：[11, 12, 22, 25, 34, 64, 90]
3.2 代码解释
- quick_sort 函数：
- 参数 low 和 high 表示当前子数组的起始和结束索引。
- 如果 low >= high，说明子数组长度 ≤1，无需排序。
- partition 返回基准值的索引 pivot_index，左右子数组分别递归排序。
- partition 函数：
- 基准值选择为最后一个元素 arr[high]。
- 指针 i 初始指向 -1（表示“小于等于区域”为空）。
- 遍历 j 从 low 到 high-1： 当 arr[j] ≤ pivot 时，i 向右移动一位，并与 arr[j] 交换位置。
- 最后将基准值 pivot 与 arr[i+1] 交换，确保基准值位于正确位置。
四、优化版本（随机选择基准值）
为了避免最坏情况（如数组已有序时，时间复杂度退化为 (O(n^2))），可随机选择基准值：
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]
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
五、测试与验证
5.1 正常测试
test_list = [64, 34, 25, 12, 22, 11, 90]
quick_sort(test_list, 0, len(test_list)-1)
print("排序后：", test_list) # 输出：[11, 12, 22, 25, 34, 64, 90]
5.2 边界测试
- 空列表：quick_sort([], 0, -1) → 无错误。
- 单元素列表：quick_sort([5], 0, 0) → 返回 [5]。
- 已排序列表：使用优化版本可避免最坏情况。
六、总结步骤
- 理解递归框架：快速排序通过递归不断缩小问题规模。
- 实现分区操作：通过双指针法交换元素，确保基准值正确归位。
- 选择基准值：随机选择可提升算法鲁棒性。
- 测试与调试：验证不同输入情况下的正确性。
七、练习题
- 基准值选择：将基准值改为第一个元素，观察代码是否仍能正确排序。
- 非递归实现：用栈模拟递归过程，实现迭代版本的快速排序。
- 稳定性验证：快速排序是不稳定排序，尝试构造测试用例验证（如 [4, 4, 2]）。
通过以上步骤，可以逐步掌握快速排序的实现逻辑，并理解其高效性与潜在优化方向。