Python 快速排序（建议收藏）

什么是快速排序？

在编程世界里，排序是一项基础又重要的操作。当你需要对一组数据进行整理，比如按成绩从高到低排列，或者按时间顺序展示日志记录，排序算法就派上用场了。在众多排序算法中，Python 快速排序 是最高效、最常用的之一。

快速排序（Quick Sort）是一种分治算法，它的核心思想是“分而治之”——把一个大问题拆成多个小问题，分别解决后再合并结果。想象一下，你有一堆杂乱无章的扑克牌，你想按花色和数字排序。你不需要一次比较所有牌，而是先选一张牌作为“基准”，把比它小的放在左边，比它大的放在右边，再对左右两堆重复这个过程。这个过程，就是快速排序的精髓。

Python 快速排序 的优势在于平均时间复杂度为 O(n log n)，在大多数实际场景下表现优异。虽然最坏情况下会退化到 O(n²)，但通过合理选择“基准”（pivot），我们可以有效避免这种情况。

快速排序的核心逻辑解析

要理解 Python 快速排序，先掌握它的三个关键步骤：

1. 选择基准值（pivot）
   从数组中选一个元素作为基准，通常是第一个、最后一个或中间位置的元素。

2. 分区操作（partition）
   重新排列数组，使得所有小于基准的元素放在左边，大于基准的元素放在右边，基准位于最终正确位置。

3. 递归处理子数组
   对基准左边和右边的子数组重复上述过程，直到每个子数组只剩一个元素。

这个过程就像一个“筛子”：每次筛出一部分正确位置的元素，剩下的继续筛，直到全部排好。

Python 实现快速排序：递归版本

下面是 Python 快速排序的完整实现代码。我们用递归方式实现，逻辑清晰，适合初学者理解。

def quick_sort(arr):
    # 如果数组长度小于等于 1，说明已经有序，直接返回
    if len(arr) <= 1:
        return arr

    # 选择基准值：这里选最后一个元素作为基准
    pivot = arr[-1]

    # 创建两个列表，分别存放小于和大于基准的元素
    left = []   # 存放小于 pivot 的元素
    right = []  # 存放大于 pivot 的元素

    # 遍历除基准外的所有元素
    for i in range(len(arr) - 1):
        if arr[i] < pivot:
            left.append(arr[i])  # 小于基准的放左边
        else:
            right.append(arr[i])  # 大于等于基准的放右边

    # 递归地对左右子数组排序，并将结果合并
    # 注意：这里使用 + 拼接，返回的是新列表
    return quick_sort(left) + [pivot] + quick_sort(right)

代码详解

• if len(arr) <= 1: return arr
  这是递归的终止条件。当数组长度为 0 或 1 时，无需排序，直接返回。

• pivot = arr[-1]
  选择最后一个元素作为基准值。你可以改成 arr[0] 或 arr[len(arr)//2]，效果类似。

• for i in range(len(arr) - 1):
  遍历除基准外的所有元素，避免重复比较。

• left.append() 和 right.append()
  根据与基准的大小关系，将元素分配到左右两个子列表。

• return quick_sort(left) + [pivot] + quick_sort(right)
  递归排序左右部分，最后用 [pivot] 拼接，形成完整有序数组。

快速排序的优化策略

虽然上面的版本逻辑清晰，但在实际应用中，有几点可以优化：

优化 1：原地排序（减少内存开销）

当前版本需要额外的 left 和 right 列表，空间复杂度为 O(n)。我们可以改为原地排序，只用一个数组，通过交换元素实现。

def quick_sort_inplace(arr, low, high):
    # 递归终止条件：当 low >= high，说明子数组长度 <= 1
    if low < high:
        # partition 函数返回基准元素的最终位置
        pivot_index = partition(arr, low, high)
        
        # 递归排序基准左边和右边的子数组
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    # 选择最后一个元素作为基准
    pivot = arr[high]
    
    # i 指向小于基准区域的边界
    i = low - 1

    # 遍历从 low 到 high-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

优化 2：随机选择基准值

如果输入数据已经有序或接近有序，选第一个或最后一个作为基准，会导致每次分区都极不平衡，时间复杂度退化到 O(n²)。为避免这种情况，可以随机选择基准。

import random

def quick_sort_random(arr, low, high):
    if low < high:
        # 随机选择基准，与最后一个元素交换
        random_index = random.randint(low, high)
        arr[random_index], arr[high] = arr[high], arr[random_index]
        
        pivot_index = partition(arr, low, high)
        quick_sort_random(arr, low, pivot_index - 1)
        quick_sort_random(arr, pivot_index + 1, high)

实际案例：用 Python 快速排序处理真实数据

假设你有一组学生考试成绩，需要按分数从高到低排序。我们可以用 Python 快速排序轻松实现。

scores = [88, 95, 72, 90, 65, 99, 83, 77, 85, 92]

print("原始成绩：", scores)

sorted_scores = quick_sort(scores)
print("升序排序：", sorted_scores)

descending_scores = sorted_scores[::-1]
print("降序排序：", descending_scores)

输出结果：

原始成绩： [88, 95, 72, 90, 65, 99, 83, 77, 85, 92]
升序排序： [65, 72, 77, 83, 85, 88, 90, 92, 95, 99]
降序排序： [99, 95, 92, 90, 88, 85, 83, 77, 72, 65]

这个例子展示了 Python 快速排序在真实场景中的实用性——只需几行代码，就能高效处理数据。

快速排序 vs 其他排序算法对比

从表格可以看出，Python 快速排序 在平均情况下的性能非常出色，是大多数场景下的首选。虽然不稳定（相等元素的相对顺序可能改变），但在大多数排序需求中不是问题。

常见问题与调试技巧

问题 1：递归深度过深导致栈溢出

当处理大量数据（如超过 10000 个元素）时，递归调用可能导致栈溢出。解决方法：

• 使用迭代方式实现快速排序
• 或者限制递归深度，对小数组改用插入排序（插入排序在小数据集上更快）

问题 2：基准选择不当导致性能下降

避免固定选择第一个或最后一个元素。推荐使用“三数取中法”：取首、中、尾三个数的中位数作为基准。

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    if arr[mid] < arr[low]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[high] < arr[low]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[high] < arr[mid]:
        arr[mid], arr[high] = arr[high], arr[mid]
    return mid

总结

Python 快速排序 是一种高效、实用的排序算法，特别适合处理大规模数据。它通过分治思想，将复杂问题分解为简单子问题，实现优雅的递归逻辑。

本文从原理到实现，从基础版本到优化策略，层层递进，帮助你真正理解快速排序的本质。无论是初学者还是中级开发者，掌握这一算法都能显著提升编程能力。

在实际开发中，你可以直接使用 Python 内置的 sorted() 或 list.sort()，它们底层也使用了优化的快速排序（或 Timsort）。但理解其原理，能让你在面对性能瓶颈时，做出更明智的选择。

记住，算法不是死记硬背的公式，而是解决问题的思维方式。当你熟练掌握 Python 快速排序，你离“算法思维”又近了一步。