快速排序（Quick Sort）算法原理与实现

快速排序是一种基于分治思想的高效排序算法，平均时间复杂度为 O(n log n)，在实际应用中广泛使用。它的核心思想是通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有元素均比另一部分的元素小，然后递归地对这两部分进行排序。

1. 基本思想

1. 选择基准值（Pivot）：从待排序数组中选取一个元素作为基准值（通常选择第一个元素、最后一个元素或随机元素）。
2. 分区（Partition）：重新排列数组，使得所有小于基准值的元素放在基准左侧，大于基准值的元素放在右侧（等于基准值的元素可任意放置）。此时基准值处于其最终排序位置。
3. 递归排序：对基准值左侧和右侧的子数组递归执行上述过程，直到子数组长度为1或0（自然有序）。

2. 分区过程详解（以 Lomuto 分区方案为例）

假设选择最后一个元素作为基准值，分区步骤如下：

• 初始化指针 i 指向分区边界（初始为起始位置）。
• 遍历数组从起始到倒数第二个元素，用指针 j 扫描：
  • 若当前元素 arr[j] 小于基准值，则将其与 arr[i] 交换，并将 i 右移一位。
• 最后将基准值（末尾元素）与 arr[i] 交换，此时基准值位于正确位置。
• 返回基准值的索引 i。

示例：对数组 [3, 1, 4, 1, 5, 9, 2] 进行分区（选择末尾元素 2 为基准）：

• 遍历过程中，小于2的元素依次与 i 位置交换：
  • j=0：3>2，不交换 → i=0
  • j=1：1<2，交换(1,3) → 数组 [1, 3, 4, 1, 5, 9, 2]，i=1
  • j=2：4>2，不交换
  • j=3：1<2，交换(1,3) → 数组 [1, 1, 4, 3, 5, 9, 2]，i=2
  • 后续元素均大于2，无交换。
• 最后交换基准值 arr[6] 与 arr[i=2] → [1, 1, 2, 3, 5, 9, 4]，返回索引2。

3. 递归排序实现

分区后，对左子数组 [0, pivotIndex-1] 和右子数组 [pivotIndex+1, end] 递归调用快速排序。

4. 时间复杂度分析

• 最佳/平均情况：每次分区将数组均匀分成两半，递归深度为 O(log n)，每层分区操作耗时 O(n)，总复杂度 O(n log n)。
• 最坏情况：当数组已有序且每次选择最大/最小元素为基准时，分区极度不平衡（一侧无元素），递归深度为 O(n)，总复杂度 O(n²)。
• 优化策略：
  • 随机选择基准值（避免最坏情况与输入顺序相关）。
  • 三数取中法（选择首、中、尾元素的中位数作为基准）。

5. 代码实现（Python）

import random

def quicksort(arr, low, high):
    if low < high:
        # 随机选择基准值并交换到末尾（避免最坏情况）
        pivot_idx = random.randint(low, high)
        arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
        
        # 分区操作
        i = low
        for j in range(low, high):
            if arr[j] < arr[high]:  # 以末尾元素为基准
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]  # 基准归位
        
        # 递归排序左右子数组
        quicksort(arr, low, i-1)
        quicksort(arr, i+1, high)

# 测试示例
arr = [3, 1, 4, 1, 5, 9, 2]
quicksort(arr, 0, len(arr)-1)
print(arr)  # 输出 [1, 1, 2, 3, 4, 5, 9]

6. 关键要点

• 稳定性：快速排序是不稳定排序（相等元素可能交换顺序）。
• 空间复杂度：递归调用栈占用 O(log n)～O(n) 空间。
• 实际性能：虽最坏情况较差，但通过优化基准选择后，在实践中通常优于归并排序和堆排序。

通过以上步骤，你可以理解快速排序的核心分治策略、分区过程的细节，以及如何通过优化提升其鲁棒性。