使用快速排序（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)

来源

2015-11-20 user1330974

您是否检查过quickselect算法？ –

您正在使用包含数组边界。你正在做这个不必要的努力。几乎所有算法都使用[start，end）更加优雅地描述。 – orlp

您在'partition'功能中混合使用'a'和'arr'。 – thefourtheye

如果您正在使用含数组边界，这是不是最方便的技巧，你就必须改变范围在递归调用[start, piv - 1]和[piv + 1, end]

原因是，你正在重新考虑每个递归中的pivot元素都在数组的左边。

带有所述更改的代码运行时没有任何堆栈溢出错误。

编辑对于很少的k值，输出是不正确的。您可能需要再次检查分区逻辑。

来源

2015-11-20 08:35:26

谢谢。我希望有一个熟悉这种算法的人（使用快速排序找到第k个最小的项目）将确认是否有可能从中心选择枢轴。我自己测试了我的quicksort分区逻辑，没有找到第k个元素的上下文，并且它工作正常。这就是为什么我决定问StackOverflow。再次感谢。 – user1330974

中间轴是绝对可能的，因为我记得基于它读取资源。我敢肯定，实施 –

@Faize Halde会让人感到困惑，呃......有点让人放心。如果你还记得来源，请随时分享。：）谢谢！ – user1330974

使用快速排序（Python）查找第k个最小项目

回答

相关问题