Python快速排序(quick sort)整体时间复杂度为何能达到O(nlogn)？

def partition(A, l, r):
    p = A[l]
    stack = A[l]
    A[l] = A[r]
    A[r] = stack
    s = l

    for i in range(l, r):
        if A[i] <= p:
            stack2 = A[i]
            A[i] = A[s]
            A[s] = stack2
            s += 1

    stack3 = A[s]
    A[s] = A[r]
    A[r] = stack3

    return s

def quicksort(A, l, r):
    if l < r:
        q = partition(A, l, r)
        quicksort(A, l, q - 1)
        quicksort(A, q + 1, r)
    return A

你提供的是标准Lomuto分区版本的快速排序实现，它的平均时间复杂度确实可以达到O(nlogn)，原因如下：

• 你观察到的单轮partition时间复杂度O(n)是正确的，该函数需要完整遍历当前待处理区间的所有元素，完成基准值定位和左右分区。
• 每一层递归的总时间开销恒定为O(n)：不管当前递归层拆分出了多少个待排序子区间，所有子区间的长度总和等于初始数组的长度n，该层所有partition调用的遍历总次数就是n，因此单层总开销固定为O(n)。
• 平均情况下递归总层数为O(logn)：如果每次分区选择的基准值能将当前区间近似拆分为两个长度相近的子区间，那么要将长度为n的数组拆分到所有子区间长度为1，总共需要的递归层数就是log₂n量级。
• 两者相乘即可得到平均时间复杂度为O(n) * O(logn) = O(nlogn)。

注意：该实现存在最坏时间复杂度O(n²)的场景。由于你固定选择区间左端点作为基准值，如果待排序数组本身已经是有序/逆序的，每次分区只会拆分出1个元素和长度为n-1的子区间，递归层数会上升到O(n)，总时间复杂度就会退化到O(n²)。可以通过随机选择基准、三数取中等方式优化降低最坏情况的触发概率。

内容的提问来源于stack exchange，提问作者Mama africa