使用快速排序(Python)查找第k个最小项目
我试图执行this video中讨论的算法,并且还在this document中。使用快速排序(Python)查找第k个最小项目
我的快速排序的代码,这取决于拾取中间元件阵列在作为枢轴(见下文),而不是由上面的文档的作者,它使用第一元件在使用的方法作为shown here in the video的数据集。
显然,我的代码不起作用(最终用完了递归限制)。我想知道是否是因为我的代码中存在一些愚蠢的错误,或者只要我从中间选择中心点,它就无法工作。
def partition(a, start, end):
# I pick the pivot as the middle item in the array
# but the algorithm shown in the video seems to
# pick the first element in the array as pivot
piv = (start + end) // 2
pivotVal = a[piv]
left = start
right = end
while left <= right:
while a[left] < pivotVal:
left += 1
while a[right] > pivotVal:
right -= 1
if left <= right:
temp = a[left]
a[left] = a[right]
a[right] = temp
left += 1
right -= 1
return left
def quicksort(a, start, end, k):
if start < end:
piv = partition(a, start, end)
if piv == (k - 1):
print("Found kth smallest: " + piv)
return a[piv]
elif piv > (k - 1):
return quicksort(a, start, piv, k)
else:
return quicksort(a, piv + 1, end, k)
myList = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quicksort(myList, 0, len(myList) - 1, 3)
print(myList)
如果您正在使用含数组边界,这是不是最方便的技巧,你就必须改变范围在递归调用[start, piv - 1]
和[piv + 1, end]
原因是,你正在重新考虑每个递归中的pivot元素都在数组的左边。
带有所述更改的代码运行时没有任何堆栈溢出错误。
编辑对于很少的k值,输出是不正确的。您可能需要再次检查分区逻辑。
谢谢。我希望有一个熟悉这种算法的人(使用快速排序找到第k个最小的项目)将确认是否有可能从中心选择枢轴。我自己测试了我的quicksort分区逻辑,没有找到第k个元素的上下文,并且它工作正常。这就是为什么我决定问*。再次感谢。 – user1330974
中间轴是绝对可能的,因为我记得基于它读取资源。我敢肯定,实施 –
@Faize Halde会让人感到困惑,呃......有点让人放心。如果你还记得来源,请随时分享。 :) 谢谢! – user1330974
您是否检查过quickselect算法? –
您正在使用包含数组边界。你正在做这个不必要的努力。几乎所有算法都使用[start,end)更加优雅地描述。 – orlp
您在'partition'功能中混合使用'a'和'arr'。 – thefourtheye