我是Python的新手，我正在练习编写代码，但我遇到了一些麻烦。
我正在尝试实现QuickSelect，以便提取K最大元素。
这是我的密码；
def partition(A, left, right):
pivot = random.randrange(left, right) # 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)
尝试实现算法以获得第5高元素：
a = get_random_array(10, 100)
print("array unsorted=" , a)
print("array sorted=", sorted(a))
print("result:" , QuickSelect(A = a, K = 5, left = 0, right = len(a)-1)) #I want the 5-th highest element
得到这个结果：
array unsorted = [71, 34, 0, 36, 26, 15, 3, 69, 93, 85]
array sorted = [0, 3, 15, 26, 34, 36, 69, 71, 85, 93]
result: 3
结果是错误的，因为3不是第5高的元素。
错误是在partition(A, left, right)中还是在QuickSelect(A, K, left, right)中？你能帮我解决吗？非常感谢。
您的代码中存在几个问题。
- 代码将
pivot视为值，但它是索引 - 在开始循环之前，应先将枢轴移开(移动到
right( - 当
K == i时，不应返回A[i]，因为i是一个相对，基于1的索引。你应该return A[q] - 这不是一个严重的问题，但
randrange(left, right)永远不会返回right，所以您可能想执行randrange(left, right + 1)或randint(left, right)
纠正后的代码：
def partition(A, left, right):
# This gets an index, not a value:
pivotindex = random.randint(left, right) # allow right to be selected
pivot = A[pivotindex] # this is the pivot value
# move the value out of the way
A[right], A[pivotindex] = A[pivotindex], A[right]
i = left - 1
for j in range(left, right):
if A[j] < pivot:
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):
if left == right:
return A[left]
q = partition(A, left, right)
i = q - left + 1
if K == i:
return A[q] # this is the element you want to return
if K < i:
return QuickSelect(A, K, left, q - 1)
else:
return QuickSelect(A, K - i, q + 1, right)
您的两个函数都有问题。您正在将pivot设置为分区函数
random.randrange(left, right)
而是将其设置为
A[right]
def partition(A, left, right):
pivot = A[right] # pick a random number as pivot
i = left
for j in range(left, right):
if A[j] <= pivot:
A[i], A[j] = A[j], A[i]
i = i+1
A[i], A[right] = A[right], A[i]
return i
在第二个函数中，将其重新修改为
def Quickselect(A, left, right, k):
if (k > 0 and k <= right - left + 1):
q = partition(A, left, right)
if (q - left == k - 1):
return A[q]
if (q - left > k - 1):
return Quickselect(A, left, q - 1, k)
return Quickselect(A, q + 1, right,
k - q + left - 1)
参考：https://www.geeksforgeeks.org/quickselect-algorithm/
区块报价