排序算法之：快速排序的分区策略优化——三数取中法（Median-of-Three）的深入实现与性能分析

我们先从一个经典问题开始：
“给定一个整数数组，使用快速排序将其升序排列，但要求在分区时采用三数取中法选择基准，以减少最坏情况发生的概率。”

1. 问题描述

快速排序的平均时间复杂度为 O(n log n)，但若每次选择的基准恰好是最小或最大值，会导致递归深度达到 O(n)，时间复杂度退化为 O(n²)。
三数取中法 是一种优化策略：

• 在待排序子数组中，选取首、尾、中间三个位置的元素。
• 将这三个元素的中位数作为基准，从而避免选择极端值。

2. 解题思路（循序渐进）

步骤一：理解基础快速排序

快速排序的核心是 分区（partition）：

1. 选择数组中的一个元素作为基准（pivot）。
2. 将数组重新排列，使所有小于基准的元素移到基准左侧，大于基准的元素移到右侧。
3. 递归地对左右子数组进行排序。

常用分区方法有 Lomuto 分区和 Hoare 分区，我们以 Lomuto 分区为例讲解优化。

步骤二：三数取中法的实现方法

假设我们要排序的区间是 arr[left...right]：

1. 计算中间索引 mid = left + (right - left) / 2。
2. 比较 arr[left], arr[mid], arr[right] 三个值。
3. 将这三个数的中位数交换到 arr[left] 位置（或 arr[right]，取决于分区写法）。
4. 以该中位数作为基准进行分区。

为什么能减少最坏情况？
因为极端值（最小或最大）被选为基准的概率大大降低，递归树更平衡。

步骤三：具体实现细节

我们使用 Lomuto 分区（以最后一个元素为基准）为例，结合三数取中：

1. 选取中位数并放到末尾（方便 Lomuto 分区）：
   • 比较 arr[left], arr[mid], arr[right]。
   • 将中位数交换到 arr[right]。
2. 以 arr[right] 为基准进行 Lomuto 分区。
3. 递归排序左右部分。

步骤四：代码示例（含注释）

def median_of_three(arr, left, right):
    """将左、中、右三个元素的中位数交换到 right 位置"""
    mid = left + (right - left) // 2
    
    # 排序 arr[left], arr[mid], arr[right]
    if arr[left] > arr[mid]:
        arr[left], arr[mid] = arr[mid], arr[left]
    if arr[left] > arr[right]:
        arr[left], arr[right] = arr[right], arr[left]
    if arr[mid] > arr[right]:
        arr[mid], arr[right] = arr[right], arr[mid]
    
    # 此时 arr[mid] 是中位数，将其交换到 right 位置（作为基准）
    arr[mid], arr[right] = arr[right], arr[mid]

def lomuto_partition(arr, left, right):
    # 先使用三数取中调整
    median_of_three(arr, left, right)
    pivot = arr[right]  # 基准是调整后的右端元素
    i = left - 1  # i 指向小于基准的区域的末尾
    
    for j in range(left, right):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # 将基准放到正确位置
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

def quicksort(arr, left, right):
    if left < right:
        pi = lomuto_partition(arr, left, right)
        quicksort(arr, left, pi - 1)
        quicksort(arr, pi + 1, right)

# 使用示例
arr = [10, 7, 8, 9, 1, 5]
quicksort(arr, 0, len(arr) - 1)
print(arr)  # 输出 [1, 5, 7, 8, 9, 10]

步骤五：性能分析

• 时间复杂度：
  平均情况 O(n log n)，最坏情况概率极低（除非数组有特殊排列，但三数取中使其几乎不可能出现连续最坏情况）。
• 空间复杂度：
  递归栈空间 O(log n)（平均），最坏 O(n)（但概率极低）。
• 优点：
  1. 显著减少已排序或接近排序数组的最坏情况。
  2. 对随机数据也有轻微性能提升。
• 缺点：
  每次分区多 3 次比较和最多 3 次交换，常数因子略增，但可忽略。

步骤六：进一步优化（可选）

1. 小数组切换为插入排序：
   当子数组长度小于某个阈值（如 16）时，使用插入排序，减少递归开销。
2. 尾递归优化：
   先递归较短的一边，较长的一边用循环处理，保证栈深度不超过 O(log n)。
3. 三路分区：
   如果数组有大量重复元素，可使用三路快速排序（3-way quicksort）。

3. 总结

三数取中法是快速排序中最实用的优化之一，它通过简单的三次比较和交换，大幅降低最坏情况的概率，且不增加算法复杂度。
实际工程中（如 C++ STL、Java 的 Arrays.sort() 基础类型排序）都采用了类似的策略来保证快速排序的稳健性。