快速排序算法：分治思想的经典应用

快速排序（Quicksort）是由 Tony Hoare 在 1960 年发明的排序算法，是最常用的排序算法之一。

算法原理

快速排序采用分治策略：

选择基准（pivot）：从数组中选择一个元素作为基准
分区（partition）：将数组分为两部分，小于基准的在左，大于基准的在右
递归：对左右两部分递归执行快速排序

基本实现

Python 实现

def quick_sort(arr):
    """
    快速排序算法
    
    Args:
        arr: 待排序数组
    
    Returns:
        排序后的数组
    """
    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)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # [1, 1, 2, 3, 6, 8, 10]

原地排序版本（更高效）

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

def quick_sort_inplace(arr, low, high):
    """
    原地快速排序
    """
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

# 使用示例
arr = [10, 7, 8, 9, 1, 5]
quick_sort_inplace(arr, 0, len(arr) - 1)
print(arr)  # [1, 5, 7, 8, 9, 10]

时间复杂度分析

最佳情况

每次分区都能将数组均匀分成两半
时间复杂度：O(n log n)

平均情况

时间复杂度：O(n log n)
这是快速排序最常见的性能表现

最坏情况

每次选择的基准都是最小或最大元素
时间复杂度：O(n²)
可以通过随机选择基准来避免

空间复杂度

递归调用栈的深度
平均：O(log n)
最坏：O(n)

优化策略

1. 随机选择基准

import random

def partition_random(arr, low, high):
    # 随机选择基准
    random_index = random.randint(low, high)
    arr[random_index], arr[high] = arr[high], arr[random_index]
    return partition(arr, low, high)

2. 三路快排（处理重复元素）

def quick_sort_3way(arr, low, high):
    if low >= high:
        return
    
    lt, i, gt = low, low, high
    pivot = arr[low]
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)

3. 小数组使用插入排序

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def quick_sort_optimized(arr, low, high):
    if high - low < 10:  # 小数组使用插入排序
        insertion_sort(arr, low, high)
        return
    
    if low < high:
        pi = partition(arr, low, high)
        quick_sort_optimized(arr, low, pi - 1)
        quick_sort_optimized(arr, pi + 1, high)

与其他排序算法比较

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定

应用场景

通用排序：大多数情况下的首选
大数据集：处理大量数据时效率高
内排序：不需要额外空间（原地排序版本）

总结

快速排序是分治思想的经典应用，具有：

✅ 平均性能优秀（O(n log n)）
✅ 原地排序，空间效率高
✅ 实现相对简单
⚠️ 最坏情况性能较差
⚠️ 不稳定排序

在实际应用中，快速排序通常是排序大量数据的首选算法。