带均匀噪声的已排序数组的快速排序优化问题

核心思路分析 #

你的判断没错，要避免快速排序最坏O(n²)的情况，关键在于选到的pivot不能是当前子数组的最小或最大值，同时要保证每次分区后左右子数组的大小尽可能均衡。结合题目中数组的特性——A[i] = i + u（u∈[-k,k]且k<<n），每个元素的实际值和它的索引i偏差极小，我们可以直接利用这个结构来确定安全的pivot。

确定性Pivot选择方案 #

因为k远小于n，数组中任意子数组的中间索引mid对应的元素A[mid]取值范围是[mid -k, mid +k]：

• 全局最小元素的上限是0 +k，而mid至少是子数组的中间位置（比如整个数组的mid = n//2），mid -k远大于0 -k，所以A[mid]不可能是全局最小值；
• 全局最大元素的下限是(n-1) -k，mid +k远小于(n-1)+k，所以A[mid]也不可能是全局最大值。

直接选择子数组的中间索引对应的元素作为pivot，就能保证每次分区后左右子数组的大小不会极端失衡，递归深度稳定在O(logn)，总时间复杂度自然是O(nlogn)。

具体实现代码（Python） #

def quick_sort(A, left, right):
    if left < right:
        # 选择子数组中间位置作为pivot
        mid = (left + right) // 2
        # 将pivot交换到子数组末尾，方便使用Lomuto分区法
        A[mid], A[right] = A[right], A[mid]
        # 执行分区，得到pivot的最终位置
        pivot_idx = partition(A, left, right)
        # 递归排序左右子数组
        quick_sort(A, left, pivot_idx - 1)
        quick_sort(A, pivot_idx + 1, right)

def partition(A, left, right):
    pivot = A[right]
    i = left - 1
    # 遍历子数组，将小于等于pivot的元素移到左侧
    for j in range(left, right):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    # 将pivot放到正确的位置
    A[i + 1], A[right] = A[right], A[i + 1]
    return i + 1

# 测试示例
n = 1000
k = 10
import random
A = [i + random.randint(-k, k) for i in range(n)]
quick_sort(A, 0, n-1)
print(A == sorted(A))  # 验证排序正确性

最坏情况验证 #

即使遇到极端噪声情况（比如所有u=k，数组变成严格递增的A[i]=i+k；或所有u=-k，数组变成严格递减的A[i]=i-k），选择中间位置的pivot依然能将数组分成大小近似相等的两部分，递归深度始终是O(logn)，每层递归的分区操作是O(n)，总时间复杂度稳定在O(nlogn)，不会退化成O(n²)。

内容的提问来源于stack exchange，提问作者Art Zabergja