使用快速排序（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個最小項目

回答

相關問題