QuickSelect算法

Question

我目前正在为我的计算机科学课做一项作业，我不知道我的代码有什么问题来执行快速选择。

def partition(a_list, first, last):
    pivot = a_list[last]
    i = first-1
    for j in range(first, last):
        if a_list[j] <= pivot:
            i += 1
            a_list[i], a_list[j] = a_list[j], a_list[i]
    a_list[i+1], a_list[last] = a_list[last], a_list[i+1]
    print(a_list)
    return i+1

def selection(a_list, first, last, k):
    pivot = a_list[last]
    pivotIndex = partition(a_list, first, last)
    if first == last:
        return a_list[k]
    elif k <= pivotIndex:
        return selection(a_list, first, pivotIndex-1, k)
    else:
        return selection(a_list, pivotIndex+1, last, k - pivotIndex)

print(selection([5,4,1,10,8,3,2], 0, 6, 1))
print(selection([5,4,1,10,8,3,2], 0, 6, 3))
print(selection([5,4,1,10,8,3,2], 0, 6, 6))
print(selection([5,4,1,10,8,3,2], 0, 6, 7))
print(selection([46, 50, 16, 88, 79, 77, 17, 2, 43, 13, 86, 12, 68, 33, 81, \
74, 19, 52, 98, 70, 61, 71, 93, 5, 55], 0, 24, 19))

在第三个print语句之后，我的代码就卡在了一个循环中，最后因为达到了最大的递归而死了。第一个输出也应该是1，我理解它为什么要这样做。但我想不出解决办法。

这是我的输出，在它最终给出达到的最大递归深度之前。(忽略正在打印的列表，它就在那里，这样我就可以看到它的分区了)

[1, 2, 5, 10, 8, 3, 4]
2
[1, 2, 5, 10, 8, 3, 4]
[1, 2, 3, 4, 8, 5, 10]
3
[1, 2, 5, 10, 8, 3, 4]
[1, 2, 3, 4, 8, 5, 10]
[1, 2, 3, 4, 8, 5, 10]
[1, 2, 3, 4, 5, 8, 10]
[1, 2, 3, 5, 4, 8, 10]
[1, 2, 3, 4, 5, 8, 10]
[1, 2, 3, 5, 4, 8, 10]
[1, 2, 3, 4, 5, 8, 10]

Answer 1

在我看来，partition函数似乎很好。主要问题与selection函数有关。它们是：

1. 混合0-索引和1-索引
2. selection函数的检验界
3. 处理递归的k值

第1点:混合0-索引和1-索引

这个例子显示了：

print(selection([5,4,1,10,8,3,2], 0, 6, 1))

您在问题中说，预期的输出是1。排序的列表[5,4,1,10,8,3,2]是[1,2,3,4,5,8,10]。在对selection函数的调用中，您分别提供了0和6作为first和last。这两个变量使用0索引.然而，对于k，您提供了1，并期望selection函数的输出为1。这利用了1-索引.

这没什么错，但事情很快就会变得混乱。我们应该规范事物。我选择对k使用0索引.

点2：selection函数的检查界

特别是，这一声明：

if first == last:

应改为：

if first >= last:

由于下列声明：

elif k <= pivotIndex:
    return selection(a_list, first, pivotIndex-1, k)
else:
    return selection(a_list, pivotIndex+1, last, k - pivotIndex)

在这两个递归调用中，有可能是first >= pivotIndex - 1和pivotIndex + 1 >= last调用selection。在这些情况下，我们知道子列表中只剩下一个元素，所以我们应该返回它。

点3:处理递归的k值

在本声明中：

return selection(a_list, pivotIndex+1, last, k - pivotIndex)

没有必要从pivotIndex中减去k。尽管下一个selection调用只考虑了从pivotIndex+1到last (包括)的子列表，但我们没有创建一个只包含从a_list[pivotIndex+1]到a_list[last]的元素的新数组，因此我们感兴趣的元素仍然位于k位置。

有了这些变化

我们可以保持partition函数的原样。下面是一个更新的selection函数：

def selection(a_list, first, last, k):
    # Handle possibility that first >= last, so we only have
    # one element remaining in the sublist
    if first >= last:
        return a_list[k]
    pivot = a_list[last]
    pivotIndex = partition(a_list, first, last)
    if k < pivotIndex:
        return selection(a_list, first, pivotIndex-1, k)
    else:
        # k is left as it is
        return selection(a_list, pivotIndex+1, last, k)

您应该将对selection的调用更改为对k使用0索引。

希望这能帮上忙！