使用“随机交换”改进快速排序以处理数组中的大量重复项

Question

如果大小为

n

的数组仅包含一个唯一数字（一个包含所有重复项的数组），那么传统的快速排序算法将创建大小为

1

和

n-1

的非常不均匀的分区。无论我们如何选择主元元素，情况都会如此。这将使此类输入的平均案例时间复杂度为 O(n^2)。

我想到了一个简单的方法来缓解这个问题。在对数组进行分区时，如果该元素恰好等于主元元素，我们可以等概率（通过抛硬币随机）选择将其视为“小于”或“大于”主元，以便重复项均匀分布分布在枢轴周围。

def partition(arr: list[int]):
  pivot = arr[-1]
  current_index = 0
  while i in range(len(arr) - 1):
    if arr[i] < pivot or (arr[i] == pivot and random.rand() < 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.rand() < 0.5

检查）

但我从未见过这种方法在任何地方被使用过。这种方法有没有被广泛使用的问题？

Answer 1

非确定性排序非常不直观，如果我传入一个已经排序的列表，我希望再次排序时顺序不会改变，但随着你的实现，它确实会改变：

import random
from typing import List

class User:
    def __init__(self, name, age):
        self.name = name
        self.age = age

def partition(users: List[User], key='name'):
    pivot = getattr(users[-1], key)
    current_index = 0
    for i in range(len(users) - 1):
        if getattr(users[i], key) < pivot or (getattr(users[i], key) == pivot and random.random() < 0.5):
            users[i], users[current_index] = users[current_index], users[i]
            current_index += 1
    # put the pivot in its place
    users[-1], users[current_index] = users[current_index], users[-1]
    # return the partition index
    return current_index

def quicksort(users: List[User], key='name'):
    if len(users) <= 1:
        return users
    else:
        pivot_index = partition(users, key)
        left_part = quicksort(users[:pivot_index], key)
        right_part = quicksort(users[pivot_index + 1:], key)
        return left_part + [users[pivot_index]] + right_part

# Example usage:
users = [User("Alice", 25), User("Bob", 30), User("Charlie", 25)]
sorted_users_by_name = quicksort(users, key='name')
sorted_users_by_age = quicksort(users, key='age')

print("Sorted by name:")
for user in sorted_users_by_name:
    print(f"{user.name} - {user.age} years old")

for i in range(10):
    sorted_users_by_age = quicksort(sorted_users_by_age, key='age')
    print(f"\nRe-sorting {i}: Sorted by age:")
    for user in sorted_users_by_age:
        print(f"{user.name} - {user.age} years old")

有输出：

Sorted by name:
Alice - 25 years old
Bob - 30 years old
Charlie - 25 years old

Re-sorting 0: Sorted by age:
Alice - 25 years old
Charlie - 25 years old
Bob - 30 years old

Re-sorting 1: Sorted by age:
Charlie - 25 years old
Alice - 25 years old
Bob - 30 years old

Re-sorting 2: Sorted by age:
Alice - 25 years old
Charlie - 25 years old
Bob - 30 years old

Re-sorting 3: Sorted by age:
Charlie - 25 years old
Alice - 25 years old
Bob - 30 years old

Re-sorting 4: Sorted by age:
Alice - 25 years old
Charlie - 25 years old
Bob - 30 years old

Re-sorting 5: Sorted by age:
Charlie - 25 years old
Alice - 25 years old
Bob - 30 years old

Re-sorting 6: Sorted by age:
Charlie - 25 years old
Alice - 25 years old
Bob - 30 years old

Re-sorting 7: Sorted by age:
Charlie - 25 years old
Alice - 25 years old
Bob - 30 years old

Re-sorting 8: Sorted by age:
Alice - 25 years old
Charlie - 25 years old
Bob - 30 years old

Re-sorting 9: Sorted by age:
Alice - 25 years old
Charlie - 25 years old
Bob - 30 years old

除了这个小小的不便之外，我认为你的解决方案很好。