实现快速排序的稳定性分析与优化

题目描述：
快速排序是一种高效的排序算法，但在标准实现中是不稳定的。本题要求你深入理解快速排序的稳定性问题，并掌握如何通过优化策略来改善其性能。

解题过程：

1. 快速排序稳定性分析
   稳定性定义：如果排序算法能够保持相等元素的相对顺序不变，则该算法是稳定的。

标准快速排序不稳定的原因：

• 分区过程中，相等元素可能被交换到不同位置
• 以最后一个元素为基准的分区示例：

  原始数组: [3a, 2, 3b, 1, 3c]  (用a,b,c区分相等的3)
  选择最后一个元素3c作为基准
  分区后可能结果: [2, 1, 3a, 3c, 3b]
  相等元素3的相对顺序被改变
  

2. 实现稳定的快速排序
   方法一：使用额外空间的三路分区

def stable_quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
    
    left = []
    middle = []
    right = []
    
    for x in arr:
        if x < pivot:
            left.append(x)
        elif x == pivot:
            middle.append(x)  # 保持相等元素的原始顺序
        else:
            right.append(x)
    
    return stable_quicksort(left) + middle + stable_quicksort(right)

方法二：原地稳定的快速排序（复杂但高效）

def stable_quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        # 三路分区
        pivot = arr[(low + high) // 2]
        i, j, k = low, low, high
        
        while j <= k:
            if arr[j] < pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j += 1
            elif arr[j] == pivot:
                j += 1
            else:
                arr[j], arr[k] = arr[k], arr[j]
                k -= 1
        
        stable_quicksort_inplace(arr, low, i - 1)
        stable_quicksort_inplace(arr, j, high)

3. 快速排序的优化策略
   优化1：基准选择优化

• 三数取中法：选择第一个、中间、最后一个元素的中位数

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    a, b, c = arr[low], arr[mid], arr[high]
    if a <= b <= c or c <= b <= a:
        return mid
    elif b <= a <= c or c <= a <= b:
        return low
    else:
        return high

优化2：小数组使用插入排序

def optimized_quicksort(arr, low=0, high=None, threshold=10):
    if high is None:
        high = len(arr) - 1
    
    if high - low + 1 <= threshold:
        insertion_sort(arr, low, high)
        return
    
    # 正常快速排序逻辑
    pivot_index = partition(arr, low, high)
    optimized_quicksort(arr, low, pivot_index - 1, threshold)
    optimized_quicksort(arr, pivot_index + 1, high, threshold)

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

优化3：尾递归优化

def tail_recursive_quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    while low < high:
        pivot_index = partition(arr, low, high)
        
        # 先处理较小的子数组
        if pivot_index - low < high - pivot_index:
            tail_recursive_quicksort(arr, low, pivot_index - 1)
            low = pivot_index + 1
        else:
            tail_recursive_quicksort(arr, pivot_index + 1, high)
            high = pivot_index - 1

4. 完整优化实现

def advanced_quicksort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    # 使用栈模拟递归，避免栈溢出
    stack = [(low, high)]
    
    while stack:
        low, high = stack.pop()
        
        if high - low + 1 <= 10:  # 小数组使用插入排序
            insertion_sort(arr, low, high)
            continue
        
        # 三数取中选择基准
        pivot_index = median_of_three(arr, low, high)
        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
        
        # 三路分区
        pivot = arr[high]
        i, j, k = low, low, high - 1
        
        while j <= k:
            if arr[j] < pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j += 1
            elif arr[j] == pivot:
                j += 1
            else:
                arr[j], arr[k] = arr[k], arr[j]
                k -= 1
        
        arr[j], arr[high] = arr[high], arr[j]
        
        # 先处理较小的子数组（尾递归优化）
        if i - low < high - j:
            if low < i - 1:
                stack.append((low, i - 1))
            if j + 1 < high:
                stack.append((j + 1, high))
        else:
            if j + 1 < high:
                stack.append((j + 1, high))
            if low < i - 1:
                stack.append((low, i - 1))

关键要点总结：

1. 稳定性：通过三路分区和保持相等元素顺序来实现
2. 性能优化：结合多种策略（基准选择、小数组优化、尾递归）
3. 实际应用：根据数据特征选择合适的优化组合
4. 空间复杂度：优化后可以控制在O(log n)的最坏情况