Python快速排序详解（从零开始掌握快速排序算法）

快速排序的步骤

1. 选择基准：从数组中选一个元素作为基准（通常选第一个、最后一个或中间元素）。
2. 分区操作（Partition）：重新排列数组，使得比基准小的元素在左边，比基准大的在右边。
3. 递归排序：对左右两个子数组分别递归执行快速排序。

Python实现快速排序

下面是一个清晰、易懂的Python快速排序实现：

def quick_sort(arr):    """    快速排序主函数    :param arr: 待排序的列表    :return: 排序后的新列表    """    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)# 测试代码if __name__ == "__main__":    numbers = [3, 6, 8, 10, 1, 2, 1]    sorted_numbers = quick_sort(numbers)    print("原始数组:", numbers)    print("排序后数组:", sorted_numbers)

代码解析

• if len(arr) <= 1：递归终止条件，空数组或单元素数组无需排序。
• pivot = arr[len(arr) // 2]：选择中间元素作为基准，避免最坏情况（如已排序数组）。
• 使用列表推导式分别构建小于、等于、大于基准的三个子列表。
• 递归调用quick_sort对左右子列表排序，最后合并结果。

时间复杂度分析

- 平均情况：O(n log n) —— 这也是快速排序广受欢迎的原因。
- 最坏情况：O(n²) —— 当每次选择的基准都是最大或最小值时（如已排序数组且选首/尾为基准）。
- 空间复杂度：O(log n) —— 由于递归调用栈的深度。

为什么学习快速排序？

掌握Python快速排序不仅能提升你的算法思维，还能帮助你在面试中脱颖而出。它是理解分治思想的经典案例，也是许多高级算法的基础。通过本教程，你已经学会了如何用Python语言实现这一高效排序方法！

现在，动手试试吧！修改测试数据，观察排序过程，加深理解。