原始顺序中的N个最小元素(性能版)codewar

def quick_select(arr, left, right, k):
    if left == right:
        return arr[:k]
    
    pivot_index = partition(arr, left, right)
    
    if k == pivot_index:
        return arr[:k]
    elif k < pivot_index:
        return quick_select(arr, left, pivot_index - 1, k)
    else:
        return quick_select(arr, pivot_index + 1, right, k)

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

def find_n_smallest(arr, n):
    if n <= 0:
        return []
    return quick_select(arr, 0, len(arr) - 1, n)

# 示例
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
n = 3
print(find_n_smallest(arr, n))  # 输出: [1, 1, 2]