Python实现快速排序的三种经典写法及算法解析

今天想熟悉一下python的基础写法，那就从最经典的快速排序来开始吧：

1、经典分治写法（原地排序）
时间复杂度：平均O(nlogn)，最坏O(n²)
空间复杂度：O(logn)递归栈空间
特点：通过左右指针交换实现原地排序

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

2、Pythonic简洁写法（非原地）
特点：利用列表推导式，代码更简洁但需要额外空间

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)

 

3、尾递归优化写法
特点：减少递归深度，避免栈溢出风险

quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    while low < high:
        pi = partition(arr, low, high)
        if pi - low < high - pi:
            quick_sort(arr, low, pi-1)
            low = pi + 1
        else:
            quick_sort(arr, pi+1, high)
            high = pi - 1
    return arr

算法核心思想：分治法+基准值选取。第一种实现最接近传统快速排序定义，第二种适合教学演示，第三种适合处理大数据集。实际使用时建议添加随机化基准值选择来避免最坏情况。