用Python搞懂快速排序算法（分治思想实践）

教主

昨天发布 /正在检测是否收录...

0 4 0

快速排序的核心是“分治”——说白了，就是选个基准值，把数组拆成两半，然后递归处理。我个人觉得这种思路很像拆解复杂问题，写代码时特别清晰。

下面是我常用的一个实现版本，不是 in-place 的，但容易理解：

def quicksort(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 quicksort(left) + middle + quicksort(right)

注意：这个版本用了额外空间，所以空间复杂度是 O(n)。如果追求空间效率，可以找 in-place 实现，但我觉得初学先掌握这个就行。

时间复杂度方面，平均 O(n log n)，最坏 O(n^2)（比如数组已排序时）。不过实际应用中，快速排序通常很快，尤其加上随机化优化后。

我记得之前做数据清洗时，用过分治类似思路，代码效率确实提升了。所以算法不只是理论，真的能用到项目中。

小结要点：