快速排序（Quick Sort）是基于分治思想的经典排序算法，其核心思想是通过“基准值”（pivot）将数组分为两部分，递归地对子数组进行排序。它的平均时间复杂度为 (O(n log n))，是实际应用中最快的排序算法之一。以下是逐步讲解实现过程：

一、快速排序的原理

1. 核心思想

快速排序通过以下步骤实现：

选择基准值（Pivot）：从数组中选择一个元素作为基准。
分区操作（Partition）：将数组分为两部分：左半部分的所有元素 ≤ 基准值；右半部分的所有元素 ≥ 基准值。
递归排序：对左右两部分递归执行相同操作，直到子数组长度为1或0。

2. 示例演示

以数组 [5, 3, 8, 4, 2] 为例：

选择基准值：例如选择最后一个元素 2 作为基准。
分区操作：将小于等于 2 的元素移到左边，大于 2 的移到右边：[2, 3, 4, 5, 8] # 分区后基准值位置固定（索引0）
递归处理子数组：对左半部分 [2]（已有序）和右半部分 [3,4,5,8] 重复上述步骤。

二、快速排序的实现步骤

1. 递归函数设计

快速排序通常通过递归实现，函数需接收待排序的子数组范围（如起始索引 low 和结束索引 high）。

2. 分区操作的实现

分区的核心是将元素与基准值比较，并交换位置：

使用双指针法：一个指针（i）记录“小于等于基准值区域”的边界，另一个指针（j）遍历数组。
当发现 nums[j] ≤ pivot 时，将 nums[j] 与 nums[i+1] 交换，i 向右移动一位。

3. 选择基准值

常见的基准值选择方式有：

选择第一个元素；
选择最后一个元素（如示例）；
选择中间元素；
随机选择（优化性能，避免最坏情况）。

三、Python代码实现

3.1 基础版本（递归实现）

def quick_sort(arr, low, high):
    if low < high:
        # 分区操作，返回基准值的最终位置
        pivot_index = partition(arr, low, high)
        # 递归排序左右子数组
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 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[i], arr[j] = arr[j], arr[i]
    # 将基准值放到正确位置
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

# 测试
test_list = [64, 34, 25, 12, 22, 11, 90]
quick_sort(test_list, 0, len(test_list)-1)
print("排序后：", test_list)  # 输出：[11, 12, 22, 25, 34, 64, 90]

3.2 代码解释

quick_sort 函数：

参数 low 和 high 表示当前子数组的起始和结束索引。
如果 low >= high，说明子数组长度 ≤1，无需排序。
partition 返回基准值的索引 pivot_index，左右子数组分别递归排序。

partition 函数：

基准值选择为最后一个元素 arr[high]。
指针 i 初始指向 -1（表示“小于等于区域”为空）。
遍历 j 从 low 到 high-1：当 arr[j] ≤ pivot 时，i 向右移动一位，并与 arr[j] 交换位置。
最后将基准值 pivot 与 arr[i+1] 交换，确保基准值位于正确位置。

四、优化版本（随机选择基准值）

为了避免最坏情况（如数组已有序时，时间复杂度退化为 (O(n^2))），可随机选择基准值：

import random

def partition_optimized(arr, low, high):
    # 随机选择基准值并交换到末尾
    pivot_index = random.randint(low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    
    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

五、测试与验证

5.1 正常测试

test_list = [64, 34, 25, 12, 22, 11, 90]
quick_sort(test_list, 0, len(test_list)-1)
print("排序后：", test_list)  # 输出：[11, 12, 22, 25, 34, 64, 90]

5.2 边界测试

空列表：quick_sort([], 0, -1) → 无错误。
单元素列表：quick_sort([5], 0, 0) → 返回 [5]。
已排序列表：使用优化版本可避免最坏情况。

六、总结步骤

理解递归框架：快速排序通过递归不断缩小问题规模。
实现分区操作：通过双指针法交换元素，确保基准值正确归位。
选择基准值：随机选择可提升算法鲁棒性。
测试与调试：验证不同输入情况下的正确性。

七、练习题

基准值选择：将基准值改为第一个元素，观察代码是否仍能正确排序。
非递归实现：用栈模拟递归过程，实现迭代版本的快速排序。
稳定性验证：快速排序是不稳定排序，尝试构造测试用例验证（如 [4, 4, 2]）。

通过以上步骤，可以逐步掌握快速排序的实现逻辑，并理解其高效性与潜在优化方向。

醋醋百科网

Good Luck To You!

如何用Python实现快速排序算法（python快速排序原理）