快速排序

9.1 快速排序的定义

快速排序 (Quick Sort) 是一种高效的排序算法，使用“分而治之”的策略。它通过选择一个支点 (pivot)，将数组分成两个子数组——小于支点的元素和大于支点的元素，然后递归地对每个子数组应用相同的过程。

快速排序算法出现是为了尽快将小元素移到左边，大元素移到右边。假设我们最小的元素在最右边，能不能迅速将它移到接近其最终位置的地方？这会大大减少不必要的比较。

工作原理：

1. 选择支点 (pivot)：

从数组中选择一个元素作为支点。可以是第一个元素、最后一个元素、中间元素或随机元素。有时是三个随机元素的平均值。

2. 分区 (partitioning)：

把所有小于支点的元素移到数组的左边，而所有大于支点的元素移到右边。结果是支点在已排序数组中的最终位置。

3. 递归应用：

对左、右子数组递归应用这个过程，不包括支点。

逐步过程

1. 选择支点。
2. 将小于支点的元素移到左边，大于支点的移到右边。
3. 递归地对子数组应用这个过程。

快速排序的时间和空间复杂度

时间复杂度：

• 最坏情况: O(n^2) — 发生在每次选择的支点都是最坏的情况下（例如数组已排序的情况下）。
• 平均情况: O(n log n) — 对于随机分布的数据。
• 最好情况: O(n log n) — 当数组每次都被均等分割。

空间复杂度：

O(log n) — 需要用于存储递归调用的栈空间，如果使用尾递归并且支点选择得当。

9.2 快速排序算法的实现

Python 实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # 基本情况：包含 0 或 1 个元素的数组已经是排序好的
    
    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)

# 示例使用：
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)
# 输出: 排序后的数组: [1, 1, 2, 3, 6, 8, 10]

算法示例

我们来举个数组的例子：[3, 6, 8, 10, 1, 2, 1]

第一次迭代：

• 支点元素: 8
• 左边元素: [3, 6, 1, 2, 1]
• 中间元素: [8]
• 右边元素: [10]

递归地排序左边部分 [3, 6, 1, 2, 1]:

• 支点元素: 1
• 左边元素: []
• 中间元素: [1, 1]
• 右边元素: [3, 6, 2]

递归地排序右边部分 [3, 6, 2]:

• 支点元素: 6
• 左边元素: [3, 2]
• 中间元素: [6]
• 右边元素: []

递归地排序左边部分 [3, 2]:

• 支点元素: 2
• 左边元素: []
• 中间元素: [2]
• 右边元素: [3]

合并结果: 左边部分是 [1, 1, 2, 3, 6]，右边部分是 [10]，中间是 [8]。

最终排序后的数组: [1, 1, 2, 3, 6, 8, 10]