面试题：Python常用算法之排序算法实现

Question

请用Python实现快速排序算法，并分析其时间复杂度和空间复杂度。同时说明在最坏情况下和平均情况下，该算法性能的差异。

Answer 1

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)

时间复杂度分析

• 平均情况：快速排序的平均时间复杂度为 $O(nlogn)$。每次划分操作将数组大致分为两个相等的部分，需要划分的次数约为 $logn$，每次划分操作遍历数组的时间复杂度为 $O(n)$，因此平均时间复杂度为 $O(nlogn)$。
• 最坏情况：当每次选择的基准点都是数组中的最大或最小值时，每次划分只能减少一个元素，需要划分 $n - 1$ 次，每次划分遍历数组的时间复杂度为 $O(n)$，所以最坏情况下时间复杂度为 $O(n^2)$。

空间复杂度分析

• 平均情况：平均空间复杂度为 $O(logn)$，这是因为递归调用需要占用栈空间，平均递归深度为 $logn$。
• 最坏情况：最坏情况下递归深度达到 $n$，空间复杂度为 $O(n)$。

最坏情况和平均情况算法性能差异

在平均情况下，快速排序能高效地将数组分成大致相等的两部分，不断递归实现快速排序，性能较好，时间复杂度为 $O(nlogn)$。而在最坏情况下，每次划分都极不均匀，导致算法退化为类似冒泡排序等 $O(n^2)$ 复杂度的算法，性能大幅下降。