python分别应用随机选择主元方法和分组中位数方法实现在n个元素中选择第k小的数的功能

随机选择主元方法：

import random

def partition(arr, left, right, pivot_idx):
    pivot_value = arr[pivot_idx]
    arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]
    store_idx = left
    for i in range(left, right):
        if arr[i] < pivot_value:
            arr[i], arr[store_idx] = arr[store_idx], arr[i]
            store_idx += 1
    arr[store_idx], arr[right] = arr[right], arr[store_idx]
    return store_idx

def select_kth_smallest(arr, left, right, k):
    if left == right:
        return arr[left]
    pivot_idx = random.randint(left, right)
    pivot_idx = partition(arr, left, right, pivot_idx)
    if k == pivot_idx:
        return arr[k]
    elif k < pivot_idx:
        return select_kth_smallest(arr, left, pivot_idx - 1, k)
    else:
        return select_kth_smallest(arr, pivot_idx + 1, right, k)

arr = [3, 2, 1, 5, 6, 4]
k = 2
print(select_kth_smallest(arr, 0, len(arr) - 1, k - 1)) # Output: 2

分组中位数方法：

import math

def find_median(arr):
    arr.sort()
    n = len(arr)
    return arr[n // 2]

def partition(arr, left, right, pivot_value):
    i = left
    for j in range(left, right):
        if arr[j] == pivot_value:
            arr[j], arr[right] = arr[right], arr[j]
        if arr[j] < pivot_value:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[right], arr[i] = arr[i], arr[right]
    return i

def select_kth_smallest(arr, left, right, k):
    if left == right:
        return arr[left]
    n = right - left + 1
    num_groups = math.ceil(n / 5)
    medians = []
    for i in range(num_groups):
        group_left = left + i * 5
        group_right = min(group_left + 4, right)
        median = find_median(arr[group_left : group_right + 1])
        medians.append(median)
    median_of_medians = select_kth_smallest(medians, 0, len(medians) - 1, len(medians) // 2)
    pivot_idx = partition(arr, left, right, median_of_medians)
    if k == pivot_idx:
        return arr[k]
    elif k < pivot_idx:
        return select_kth_smallest(arr, left, pivot_idx - 1, k)
    else:
        return select_kth_smallest(arr, pivot_idx + 1, right, k)

arr = [3, 2, 1, 5, 6, 4]
k = 2
print(select_kth_smallest(arr, 0, len(arr) - 1, k - 1)) # Output: 2