在Python中使用QuickSelect查找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

代码中有几个问题。

• 代码将pivot视为一个值，但它是一个索引。当K == i不应返回< code >D9时，在启动循环
• 之前，应首先将支点移开(到right)，因为i是一个相对的、基于1的索引。您应该return A[q]
• Not一个严重的问题，但是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)

Answer 2

你的两种功能都有问题。您正在像在分区函数中一样设置枢轴。

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/

区块报价