如果大小为n的数组只包含一个唯一数字(具有所有重复项的数组)，则传统的快速排序算法将创建大小为1和n-1的非常不均匀的分区.无论我们如何 Select 枢轴元素，情况都是如此.这将使此类输入的平均用例时间复杂性为O(n^2).
我想了一个简单的方法来缓解这个问题.在对数组进行分区时，如果元素恰好等于枢轴元素，我们可以(通过掷硬币的方式随机) Select 将其视为"小于"或"大于"枢轴，以便在枢轴周围均匀分布副本.
def partition(arr: list[int]):
pivot = arr[-1]
current_index = 0
for i in range(len(arr) - 1):
if arr[i] < pivot or (arr[i] == pivot and random.random() < 0.5):
arr[i], arr[current_index] = arr[current_index], arr[i]
current_index += 1
# put the pivot in its place
arr[-1], arr[current_index] = arr[current_index], arr[-1]
# return the partition index
return current_index
(强调arr[i] == pivot and random.random() < 0.5支票)
但我从未见过这种方法在任何地方被使用.这种方法有没有被广泛使用的问题？