隨機化快速排序

import random

def randomized_quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return randomized_quicksort(left) + mid + randomized_quicksort(right)

def randomized_quickselect(arr, k):
    """找到第 k 小的元素 (0-indexed)"""
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    if k < len(left):
        return randomized_quickselect(left, k)
    elif k < len(left) + len(mid):
        return pivot
    else:
        return randomized_quickselect(right, k - len(left) - len(mid))

# 比較：固定 pivot vs 隨機 pivot
import time
for n in [1000, 10000]:
    arr = list(range(n))
    random.shuffle(arr)
    start = time.time()
    randomized_quicksort(arr[:])
    t1 = time.time() - start
    print(f"n={n}: 隨機 pivot = {t1:.4f}s")