快速排序算法详解

算法简介

快速排序（Quick Sort）是一种高效的排序算法，由Tony Hoare在1960年提出。它采用分治策略，平均时间复杂度为 O(n log n)。

基本思想

快速排序的核心思想是：

1. 选择一个基准元素（pivot）
2. 将数组分成两部分：小于基准的和大于基准的
3. 递归地对这两部分进行排序

代码实现

def quicksort(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 quicksort(left) + middle + quicksort(right)

复杂度分析

最佳时间复杂度：O(n log n)

平均时间复杂度：O(n log n)

最坏时间复杂度：O(n²)

空间复杂度：O(log n)