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

题目描述
快速排序的稳定性是一个重要的面试考点。稳定性指的是排序算法能否保持相等元素的原始相对顺序。我们将深入分析快速排序不稳定的原因，探讨如何实现稳定版本，并讨论相关的优化策略。

基本概念

1. 稳定性定义：如果排序算法能够保持相等键值元素的原始相对顺序，则该算法是稳定的
2. 标准快速排序通常是不稳定的，因为partition过程中可能改变相等元素的相对位置

不稳定性分析
标准快速排序的不稳定性主要来源于partition过程：

def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素作为基准
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:  # 注意这里的"<="关系
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 交换可能破坏稳定性
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

不稳定性示例
考虑数组：[3a, 2, 3b, 1]（3a和3b表示值相等的不同元素）

• 选择最后一个元素1作为基准
• 经过partition后，3a和3b的相对位置可能改变

实现稳定快速排序的方法

方法一：额外空间法

def stable_quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    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 stable_quick_sort(left) + middle + stable_quick_sort(right)

方法二：索引追踪法

def stable_quick_sort_inplace(arr):
    def sort_with_indices(indices):
        if len(indices) <= 1:
            return indices
        
        pivot_idx = indices[len(indices)//2]
        pivot_val = arr[pivot_idx]
        
        left, middle, right = [], [], []
        
        for idx in indices:
            if arr[idx] < pivot_val:
                left.append(idx)
            elif arr[idx] == pivot_val:
                # 保持原始索引顺序
                if idx <= pivot_idx:
                    middle.insert(0, idx)  # 在相等元素中保持稳定性
                else:
                    middle.append(idx)
            else:
                right.append(idx)
        
        return sort_with_indices(left) + middle + sort_with_indices(right)
    
    sorted_indices = sort_with_indices(list(range(len(arr))))
    return [arr[i] for i in sorted_indices]

稳定性优化策略

策略一：三路划分（Dutch National Flag）

def three_way_quicksort(arr, low, high):
    if low >= high:
        return
    
    # 三路划分：将数组分为 <pivot, ==pivot, >pivot 三部分
    lt, i, gt = low, low, high
    pivot = arr[low]  # 选择第一个元素作为基准
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    # 递归处理左右两部分
    three_way_quicksort(arr, low, lt-1)
    three_way_quicksort(arr, gt+1, high)

策略二：稳定划分算法

def stable_partition(arr, low, high):
    """实现稳定的partition操作"""
    pivot = arr[high]
    n = high - low + 1
    temp = [0] * n
    
    # 第一次遍历：收集小于pivot的元素
    left = 0
    for i in range(low, high+1):
        if arr[i] < pivot:
            temp[left] = arr[i]
            left += 1
    
    # 第二次遍历：收集等于pivot的元素（保持顺序）
    equal_start = left
    for i in range(low, high+1):
        if arr[i] == pivot:
            temp[left] = arr[i]
            left += 1
    
    # 第三次遍历：收集大于pivot的元素
    right_start = left
    for i in range(low, high+1):
        if arr[i] > pivot:
            temp[left] = arr[i]
            left += 1
    
    # 复制回原数组
    for i in range(n):
        arr[low + i] = temp[i]
    
    return equal_start, right_start - 1

性能分析

时间复杂度对比

• 标准快速排序：平均O(nlogn)，最坏O(n²)
• 稳定快速排序：平均O(nlogn)，但常数因子较大
• 空间复杂度：标准版本O(logn)，稳定版本O(n)

适用场景分析

1. 需要稳定性：使用稳定版本或三路划分
2. 内存敏感：使用标准不稳定版本
3. 大量重复元素：三路划分效率更高

面试要点总结

1. 理解不稳定性根源：partition过程中的元素交换
2. 掌握实现稳定性的方法：额外空间法、索引追踪法
3. 了解优化策略：三路划分、稳定partition
4. 能够分析时间/空间复杂度的trade-off
5. 根据具体场景选择合适的变体