使用 QuickSelect 在 Python 中查找第 K 个最大的元素

Question

我是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)？你能帮我解决一下吗？谢谢！

Answer 1

您的两个函数都有问题。您在分区函数

中设置数据透视表

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/

块引用

Answer 2

您的代码中存在几个问题。

代码将 pivot 视为 value，但它是 index.
在开始循环之前，首先应将枢轴移开（到 right）
当 K == i 时，您不应该 return A[i]，因为 i 是一个 relative，基于 1 的索引。你应该return A[q]
不是一个严重的问题，但是 randrange(left, right) 永远不会 return 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)

使用 QuickSelect 在 Python 中查找第 K 个最大的元素

Find K-th largest element with QuickSelect in Python

python

arrays

algorithm

quickselect