難以實施QuickSort

我一直在嘗試實現2天內的快速排序（看起來像我的編程技能正在生鏽）。我不知道我做錯了什麼。我即將放棄，所以我想我應該參考討論論壇。難以實施QuickSort

這裏是我試圖在python中實現的代碼。但它沒有給出預期的結果。任何人都可以請指出我做錯了什麼？

def QuickSort(A,p,r): 

if p < r: 
    pivotIndex = Partition(A,p,r) 
    QuickSort(A,p,pivotIndex-1) 
    QuickSort(A,pivotIndex+1,r) 
    return A 
def Partition(A,p,r): 

m = A[p] 
i = p+1 
for j in range(p+1 , r): 
    if A[j] < m: 
     A[j] , A[i] = A[i] , A[j] 
     i+=1 
A[p], A[i-1] = A[i-1] , A[p] 
return i-1

測試輸入輸出是：

>>>QuickSort([9,8,7,6,5,4,3,2,1],0,9) 
[1, 3, 5, 6, 7, 4, 8, 2, 9]

，我將非常感激如果有人幫助我在執行本。

Regards

來源

2013-07-15 InspiredCoder

'快速排序（A [0：pivotIndex]）'就已經排除了'pivotIndex'，所以我不認爲你不需要減去1. –

我已經完成了這項工作，但我仍然得到相同的結果：/ – InspiredCoder

您的單字母命名方案不必難以破譯。如果你使用了更多的信息名稱，人們可以更容易地提供幫助。 – user2357112

我已經想出了答案。看來我是路過一少的快速排序法

def QuickSort(A,p,r): 
    if r-p <= 1: return 
    pivotIndex = Partition(A,p,r) 
    QuickSort(A,p,pivotIndex) 
    QuickSort(A,pivotIndex+1,r) 
    return A 
def Partition(A,p,r): 

    m = A[p] 
    i = p+1 

    for j in range(p+1 , r): 
     if A[j] < m: 
      A[j] , A[i] = A[i] , A[j] 
     i= i + 1 
    A[p], A[i-1] = A[i-1] , A[p] 
    return i-1

它是正確執行

來源

2013-07-15 18:33:42 InspiredCoder

當我運行這個時，我得到[8,7,6,5,4,3,2,1,9] ... – Ma3x

我得到這[1,2,3,4,5,6,7,8 ，9] – InspiredCoder

好的，如果它適合你:) – Ma3x

切片不返回原始列表的視圖;它會從舊列表中的數據中創建一個新列表。這意味着對QuickSort的遞歸調用不會更改原始列表。

來源

2013-07-15 17:22:04 user2357112

嗯，我應該在代碼中更改什麼？ – InspiredCoder

您的函數是否使用索引進行排序而不是切分列表。 – user2357112

其實問題是我想以同樣的方式做。你能建議任何其他方式，以便我只能傳遞一個參數給函數（即列表）？ – InspiredCoder

您可以嘗試在一行代碼此實現：

def QuickSort(list): 
    return [] if list==[] else QuickSort([x for x in list[1:] if x < list[0]]) + [list[0]] + QuickSort([x for x in list[1:] if x >= list[0]]) 

print QuickSort([9,8,7,6,5,4,3,2,1])

來源

2013-07-15 17:25:47 amatellanes

該算法的平均複雜度爲O（n^2），而Quicksort爲O（n log n）。另外，內存開銷是O（n）而不是O（log n）。 – cababunga

看來你想保持左側轉動並跳過它，但並沒有好起來，所以我只是將其移動到數組的末尾，並相應地減少了迭代索引，然後顛倒了分區後交換（以考慮樞軸移動）。

def Partition(A,p,r): 

    m = A[p] 
    A[p], A[r] = A[r], A[p] 
    i = p 
    for j in range(p, r): 
    if A[j] < m: 
     A[j] , A[i] = A[i] , A[j] 
     i+=1 
    A[r], A[i] = A[i] , A[r] 
    return i

我認爲你可以與左側樞軸做到這一點，但你將不得不改變循環方向我想，但我不知道。

編輯：對不起我忘了補充呼叫然後快速排序（[9,8,7,6,5,4,3,2,1]，0， 8）中，由於指數現在是包括性的。

來源

2013-07-15 18:33:36 Ma3x

難以實施QuickSort

回答

相關問題