使用QuickSelect-Python选择K个最大的元素

Question

我是Python的新手，我正在练习编写代码，但我遇到了一些麻烦。

我正在尝试实现一种基于QuickSelect的算法，其中可以提取K个最大元素。

因此，在我实现QuickSelect算法并使用它来查找阵列A中的第K个最大元素之前。然后使用函数k_largest_quickselect(A, K)扫描阵列A，以收集大于或等于用QuickSelect找到的第K元素的K个元素。最后，对收集的元素进行排序。

这是我实现的代码：

def partition(A, left, right): 
pivot = random.choice(A)  # pick a random number as pivot
i = left - 1
for j in range(left, right): 
if A[j] <= pivot: 
i = i+1 
A[i], A[j] = A[j], A[i]
A[i+1], A[right] = A[right], A[i+1] 
return i+1
def QuickSelect(A, K, left, right): # Array, K-th element
if left == right:
return A[left]
q = partition(A, left, right)
i = q - left + 1
if K == i:
return A[i]
if K < i:
return QuickSelect(A, K, left, q - 1)
else:
return QuickSelect(A, K - i, q + 1, right)

def k_largest_quickselect(A, K):
B = [i for i in A if i >= QuickSelect(A = A, K = K, left = 0, right = len(a)-1)] # elements >= the K-th element found with QuickSelect
B.sort(reverse = True)
return B

我试着测试算法

a = get_random_array(10, 10)
print("Array a = " + str(a))
print(sorted(a)[-3:])
print(sorted(k_largest_quickselect(a, 3))) # from array a select the 3 highest number

得到这个结果

Array a = [0, 3, 0, 6, 2, 5, 1, 8, 1, 9]
[6, 8, 9]
[2, 5, 6, 6, 9, 9]

正如您所看到的，通过使用函数k_largest_quickselect(A = a, K = 3)，我没有得到数组中最大的3个元素。

求你了，你能帮我解决这个问题吗？非常感谢！

Answer 1

这里有一种不同的算法方法：

def kSelect(a, k):
largestElements = []

for interation in range(0,k):
largestElementInArray = max(a)
largestElements.append(largestElementInArray)
a.remove(largestElementInArray)
return largestElements

不确定这是否是你想要实现的。。？