直接回答

快速排序基于分治：从数组中选一个基准元素（pivot），一趟划分把小于基准的放左边、大于的放右边，基准落到最终位置；再递归排序左右两个子数组。平均时间复杂度 O(n log n)，最坏 O(n²)，原地排序、不稳定。

展开解析

划分常用 Lomuto 或 Hoare 方案：Lomuto 维护一个"小于区"指针 i，遍历中遇到小于 pivot 的元素就换到 i 处。最坏情况出现在每次划分极不平衡时，比如数组已有序且总取首元素作 pivot，退化成 O(n²)；对策是随机选 pivot 或三数取中。递归深度平均 O(log n)，故空间复杂度 O(log n)；可对较短的递归分支迭代化避免栈溢出。工程优化：小规模子数组（如长度 < 16）切换插入排序、三路快排处理大量重复键。追问方向：为什么平均是 O(n log n)（递归树每层总划分代价 O(n)，期望树深 O(log n)）、与归并排序的取舍。

示例

def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    p = partition(a, lo, hi)
    quicksort(a, lo, p - 1); quicksort(a, p + 1, hi)