快速排序

快速排序（Quicksort）是一种高效的分治排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）于1959年提出。它通过选择一个“基准”（pivot），将数组分为两部分，一部分小于基准，另一部分大于基准，然后递归地对子数组排序。快速排序的平均时间复杂度为$O(n\log n)$，最坏情况下为$O(n^2)$，但在实际应用中通常表现优异。

算法原理

快速排序的核心思想是分治法（Divide and Conquer），具体步骤如下： 1. 选择基准（Pivot Selection）：从数组中选择一个元素作为基准（通常选择第一个、最后一个或随机元素）。 2. 分区（Partitioning）：重新排列数组，使得所有小于基准的元素移到基准左侧，大于基准的元素移到右侧。此时基准处于其最终位置。 3. 递归排序（Recursion）：对基准左侧和右侧的子数组递归地应用快速排序。

递归的终止条件是子数组的长度为0或1（已排序）。

分区过程

分区是快速排序的关键步骤，以下是一个常见的实现方式（Lomuto分区方案）： 1. 选择最后一个元素作为基准（pivot）。 2. 初始化一个指针`i`，指向数组的起始位置。 3. 遍历数组，若当前元素小于基准，则将其与`i`位置的元素交换，并递增`i`。 4. 最后将基准与`i`位置的元素交换，此时`i`即为基准的最终位置。

graph TD A[选择基准] --> B[分区操作] B --> C[递归左子数组] B --> D[递归右子数组]

代码实现

以下是快速排序的Python实现（使用Lomuto分区方案）：

  
def quicksort(arr, low, high):  
    if low < high:  
        pivot_index = partition(arr, low, high)  
        quicksort(arr, low, pivot_index - 1)  # 递归排序左子数组  
        quicksort(arr, pivot_index + 1, high) # 递归排序右子数组  

def partition(arr, low, high):  
    pivot = arr[high]  # 选择最后一个元素作为基准  
    i = low            # 初始化指针i  
    for j in range(low, high):  
        if arr[j] < pivot:  
            arr[i], arr[j] = arr[j], arr[i]  # 交换元素  
            i += 1  
    arr[i], arr[high] = arr[high], arr[i]    # 将基准放到正确位置  
    return i  

# 示例  
arr = [10, 7, 8, 9, 1, 5]  
quicksort(arr, 0, len(arr) - 1)  
print("排序后的数组:", arr)

输出：

  
排序后的数组: [1, 5, 7, 8, 9, 10]  

优化策略

1. 随机化基准：避免最坏情况（如数组已排序），随机选择基准。 2. 三数取中法：选择第一个、中间和最后一个元素的中位数作为基准。 3. 尾递归优化：减少递归栈深度。

时间复杂度分析

• 平均情况：$O(n\log n)$（每次分区将数组分为近似相等的两部分）。
• 最坏情况：$O(n^2)$（如数组已排序且基准选择不当）。
• 空间复杂度：$O(\log n)$（递归栈空间）。

实际应用

快速排序广泛应用于： 1. 编程语言标准库（如C++的`std::sort`、Java的`Arrays.sort`）。 2. 大数据处理（因其缓存友好性）。 3. 需要高效排序的场景（如数据库索引构建）。

案例：排序用户年龄

假设有一个用户年龄列表`[25, 12, 30, 8, 42]`，快速排序的执行过程如下： 1. 选择基准`42`（最后一个元素），分区后数组为`[25, 12, 30, 8, 42]`。 2. 递归排序左子数组`[25, 12, 30, 8]`，选择基准`8`，分区后为`[8, 12, 30, 25]`。 3. 继续递归直到所有子数组有序，最终结果为`[8, 12, 25, 30, 42]`。

与其他排序算法对比

• 归并排序：稳定且时间复杂度恒为$O(n\log n)$，但需要额外空间。
• 堆排序：时间复杂度为$O(n\log n)$，但缓存局部性较差。
• 插入排序：对小规模数据更高效（常作为快速排序的优化补充）。

总结

快速排序因其高效性和原地排序特性成为最常用的排序算法之一。理解其分区过程和递归思想对掌握分治算法至关重要。实际应用中需注意基准选择策略以避免最坏情况。