快速选择算法

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，我理解它为什么这么做。但我想不出解决办法。在

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

^{pr2}$

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和{}分别提供为first和{}。这两个变量使用0索引。但是，对于k，您提供了1，并期望{}函数的输出是1。这将使用1索引。在

这没什么错，但事情很快就会变得混乱。我们应该把事情标准化。我选择对k使用0索引。在

第二点：检查selection函数的边界

特别是，这一声明：

^{pr2}$

应改为：

if first >= last:

因为以下陈述：

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

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

要点3：处理递归的k值

在本声明中：

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

没有必要从k中减去pivotIndex。即使下一个selection调用只考虑从pivotIndex+1到{}（包括这两个）的子列表，我们并没有创建一个只包含从a_list[pivotIndex+1]到{}的元素的新数组，因此我们感兴趣的元素仍然位于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索引。在

希望有帮助！在