🧮 快速排序 (Quick Sort)

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

📖 算法简介 / Introduction

快速排序是一种高效的分治排序算法，采用递归和分区策略。

Quick sort is an efficient divide-and-conquer sorting algorithm using recursion and partitioning.

💡 算法原理 / Principle

选择一个基准元素，将数组分为两部分，小于基准的在左，大于基准的在右，递归排序两部分。

Select a pivot element, partition the array into two parts - elements less than pivot on left, greater on right, then recursively sort both parts.

📝 代码实现 / Implementation

def 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)

✨ 示例 / Example

数组 [3, 6, 8, 10, 1, 2, 1] 排序后为 [1, 1, 2, 3, 6, 8, 10]。

Array [3, 6, 8, 10, 1, 2, 1] becomes [1, 1, 2, 3, 6, 8, 10] after sorting.

🎯 适用场景 / Scenarios

大规模数据排序, 需要稳定性能, 原地排序需求

Large datasets, Requiring stable performance, In-place sorting requirements

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异