我有实现这里讨论的快速选择的小型 python 代码。
import random
def Quickselect(A, k):
if not A:
return
pivot = random.choice(A)
i = 0
A1 = []
A2 = [] # Two new arrays A1, A2 to store the split lists
for i in range(len(A)):
if A[i] < pivot :
A1.append(A[i])
else:
A2.append(A[i])
if k < len(A1):
return Quickselect(A1, k)
if k > len(A) - len(A2):
return Quickselect(A2, k-(len(A) - len(A2)))
else:
return pivot
pass
def main():
A = [45,1,27,56,12,56,88]
print(Quickselect(A,2))
pass
我似乎遇到了一个随机错误。有什么事吗?
编辑:实施random.choice
而不是random.randint
. 上面的代码似乎工作正常。感谢用户搅拌机。