這個quicksort的實現有什麼問題？ 。

Question

我想實現快速排序算法中Cormey描述選擇支點作爲最右邊的元素等，算法導論：

這裏是我的Python實現：

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

def quicksort(A, p, r): 
    if p < r: 
     q = partition(A, p, r) 
     quicksort(A, p, q-1) 
     quicksort(A, q+1, r) 

但是，如果我嘗試像這樣測試它：

A = [2, 8, 7, 1, 3, 5, 6, 4] 
quicksort(A, 0, len(A)-1) 
print(A) 

我得到這是沒有排序，但只是一次分配一個數組：

[2, 3, 1, 4, 5, 7, 8, 6] 

（即，）的4的左（右所有元素都是小（比它更大））。似乎對quicksort的遞歸調用在輸入數組A上不起作用，如調用partition。我怎樣才能解決這個問題？

Answer 1

錯誤在partition，正好在for j in range(p, r-1):： 它必須是for j in range(p, r):。

發生這種情況是因爲在Python中，停止索引未包含在範圍內，但該算法意在包含r-1，因此必須在r處停止以包含r-1。