我目前正在为我的计算机科学课做作业,但我无法弄清楚我的代码在执行快速选择时出了什么问题。
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]
请您参考如下方法:
partition 函数对我来说似乎没问题。主要问题与 selection 功能有关。它们是:
- 混合 0 索引和 1 索引
- 检查
selection函数的边界 - 处理递归的
k值
要点 1:混合 0-indexing 和 1-indexing
这个例子展示了它:
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分别。这 2 个变量使用 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 在这 2 个对 selection 的递归调用中的任何一个中都是可能的.在那些情况下,我们知道子列表中只剩下 1 个元素,所以我们应该直接返回它。
要点 3:处理递归的 k 值
在这个声明中:
return selection(a_list, pivotIndex+1, last, k - pivotIndex)
没有必要从 k 中减去 pivotIndex。即使下一个 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 索引。
希望对您有所帮助!
