🚀 快速排序 (Quick Sort)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 排序 (Sorting)
时间复杂度 / Time Complexity: 平均 O(n log n)，最坏 O(n²)
空间复杂度 / Space Complexity: O(log n)

📖 算法简介 / Introduction

快速排序是一种分治排序算法，通过选择基准元素将数组划分为两部分，递归排序。

Quick Sort is a divide-and-conquer sorting algorithm that partitions the array around a pivot element and recursively sorts the sub-arrays.

💡 算法原理 / Principle

1. 选择基准：选取数组最后一个元素作为基准（也可随机选取）
2. 分区：遍历数组，将小于基准的元素移到左边，大于基准的移到右边
3. 递归：对左右两部分递归执行上述过程

核心思想：基准元素最终位置即最终排序位置。

Key Idea: The pivot element ends up in its final sorted position, and we recursively sort the left and right parts.

📝 代码实现 / Implementation

def quick_sort(arr, low, high):
    """快速排序主函数"""
    if low < high:
        # p 是分区后基准的位置
        p = partition(arr, low, high)
        # 递归排序左半部分
        quick_sort(arr, low, p - 1)
        # 递归排序右半部分
        quick_sort(arr, p + 1, high)

def partition(arr, low, high):
    """ Lomuto 分区方案 """
    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

# 简洁版（使用 Python 语言特性）
def quick_sort_pythonic(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_pythonic(left) + middle + quick_sort_pythonic(right)

✨ 示例 / Example

原始数组: [64, 34, 25, 12, 22, 11, 90]
         ↓ 选择基准 22，分区后
左半部分: [11, 12]     右半部分: [25, 64, 90]
         ↓ 继续排序         ↓ 继续排序
最终结果: [11, 12, 22, 25, 34, 64, 90]

分步演示：
Step 1: pivot = 22 → [11, 12, 22, 64, 34, 25, 90]
Step 2: 左[11, 12], 右[64, 34, 25, 90]
Step 3: pivot = 90 → [11, 12, 22, 25, 34, 64, 90]
...依此类推

🎯 适用场景 / Scenarios

• 通用排序需求：日常开发中的数组排序
• 大数据排序：原地排序，空间效率高
• 查找第 K 大/小元素：基于 partition 的思想

vs 归并排序：快速排序是原地排序，空间效率高，但不稳定；归并排序稳定但需要 O(n) 额外空间。

⚠️ 注意事项 / Notes

• 最坏情况：当数组已经有序时，退化为 O(n²)。解决方案：随机化基准或三数取中。
• 稳定性：快速排序是不稳定排序，相同元素的相对位置可能改变。

🔄 扩展阅读 / Further Reading

• 对比学习：归并排序 vs 快速排序的时间空间复杂度
• 面试高频题：Top K 问题、三数取中、荷兰国旗问题
• 优化策略：尾递归优化、小数组切换到插入排序