快速排序的优化：三数取中法（Median-of-Three）

题目描述：在标准快速排序中，如果总是选择第一个或最后一个元素作为基准（pivot），在数组已经有序或逆序时会导致最坏情况时间复杂度O(n²)。请实现使用"三数取中法"选择基准的快速排序优化版本，即从子数组的首、中、尾三个元素中选取中位数作为基准。

解题过程：

1. 问题分析

   • 标准快速排序的最坏情况发生在每次划分都极不平衡时
   • 三数取中法通过选择更接近中位数的基准，减少最坏情况发生的概率
   • 需要实现一个辅助函数来找出三个元素的中位数

2. 中位数选择函数实现

   def median_of_three(arr, low, high):
       mid = (low + high) // 2
   
       # 对三个元素进行排序
       if arr[low] > arr[mid]:
           arr[low], arr[mid] = arr[mid], arr[low]
       if arr[low] > arr[high]:
           arr[low], arr[high] = arr[high], arr[low]
       if arr[mid] > arr[high]:
           arr[mid], arr[high] = arr[high], arr[mid]
   
       # 中位数放在high-1位置，便于后续划分
       arr[mid], arr[high-1] = arr[high-1], arr[mid]
       return arr[high-1]
   

3. 划分函数优化

   def partition(arr, low, high):
       # 使用三数取中法选择基准
       pivot = median_of_three(arr, low, high)
   
       # 将基准放在high-1位置，从low+1和high-2开始划分
       i = low + 1
       j = high - 2
   
       while True:
           while arr[i] < pivot:
               i += 1
           while arr[j] > pivot:
               j -= 1
   
           if i >= j:
               break
   
           arr[i], arr[j] = arr[j], arr[i]
           i += 1
           j -= 1
   
       # 将基准放回正确位置
       arr[i], arr[high-1] = arr[high-1], arr[i]
       return i
   

4. 递归实现

   def quick_sort_optimized(arr, low, high):
       # 当子数组长度大于3时使用三数取中法
       if high - low > 2:
           pivot_index = partition(arr, low, high)
           quick_sort_optimized(arr, low, pivot_index - 1)
           quick_sort_optimized(arr, pivot_index + 1, high)
       else:
           # 对小数组使用插入排序（另一种优化）
           insertion_sort(arr, low, high)
   

5. 小数组优化

   def insertion_sort(arr, low, high):
       for i in range(low + 1, high + 1):
           key = arr[i]
           j = i - 1
           while j >= low and arr[j] > key:
               arr[j + 1] = arr[j]
               j -= 1
           arr[j + 1] = key
   

6. 完整算法流程

   • 检查子数组长度，小于阈值时使用插入排序
   • 对首、中、尾三个元素排序，选择中位数作为基准
   • 将基准放在合适位置，进行标准划分
   • 递归排序左右两个子数组

这种优化将快速排序的最坏情况概率从特定模式降低到随机情况，平均时间复杂度保持O(n log n)，常数因子更优。