0

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

4

2 回答 2

0

您的代码中有几个问题。

  • 该代码将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)
于 2021-06-13T12:58:01.140 回答
0

您的两个功能都有问题。您正在将枢轴设置为分区函数

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/

块引用

于 2021-06-13T12:39:40.553 回答