深入理解快速排序算法

核心原理

快速排序（Quick Sort）基于分治法（Divide and Conquer）。其核心逻辑是在数组中选择一个基准值（Pivot），将数组划分为两部分：小于基准值的元素放在左侧，大于基准值的元素放在右侧，随后递归地对左右子数组进行排序。

时间复杂度分析

• 平均时间复杂度：$O(n \log n)$。在基准值能够均匀划分数组时，递归树的深度为 $\log n$，每层划分的时间为 $O(n)$。
• 最坏时间复杂度：$O(n^2)$。当数组已经有序或极度不平衡时，递归树退化为链表，深度为 $n$。
• 空间复杂度：$O(\log n)$，主要来源于递归调用栈。

Lomuto 分区法代码实现

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

优化策略

为避免最坏情况，工程中常使用随机化基准值或三数取中法（取首、尾、中间三个数的中位数作为基准），结合在数据量较小时切换为插入排序以提升常数级性能。