如何改進我的快速排序算法（Python）

Question

閱讀了快速排序算法後，我決定在查看任何代碼之前編寫自己的實現。下面的代碼是我想出的。在比較我的代碼和其他實現時，我觀察到，不是從快速排序函數返回排序後的數組，而是其他實現傾向於利用列表的可變性，並簡單地在未排序的數組上運行該函數，然後將排序數組而不必參考函數調用。我很好奇與我的代碼和我正在使用的書中的代碼的空間時間比較，我在下面提供了這些代碼。我假設從時間上看，算法的表現相當相似，也許我正在執行的級聯操作有負面影響？在空間方面，因爲我沒有直接修改輸入數組，所以我假設我正在創建/返回一個明顯效率低下的新數組，這很重要，因爲快速排序合併排序的主要優點是保存的空間。總的來說，我只是尋找一些額外的見解和任何方式來提高我的算法的效率。

我的代碼：

from random import randint 

def quick(arr): 
    if len(arr) == 1: 
    return arr 
    else: 

    pivot = arr[0] 
    R = len(arr)-1 
    L = 1 

    while L <= len(arr)-1 and R >= 1: 
     if R == L: 
      if arr[0] > arr[R]: 
       arr[0], arr[R] = arr[R], arr[0] 
      break 
     if arr[R] >= pivot: 
      R = R - 1 
      continue 
     if arr[L] <= pivot: 
      L = L + 1 
      continue 
     arr[L], arr[R] = arr[R], arr[L] 
    return quick(arr[:R]) + quick(arr[R:]) 

print quick([randint(0,1000) for i in range(1000)]) 

我使用這本書，解決問題用算法和使用Python通過布拉德 - 米勒和大衛Ranum數據結構，提供了這種快速排序代碼：

def quickSort(alist): 
    quickSortHelper(alist,0,len(alist)-1) 

def quickSortHelper(alist,first,last): 
    if first<last: 

    splitpoint = partition(alist,first,last) 

    quickSortHelper(alist,first,splitpoint-1) 
    quickSortHelper(alist,splitpoint+1,last) 


def partition(alist,first,last): 
    pivotvalue = alist[first] 

    leftmark = first+1 
    rightmark = last 

done = False 
while not done: 

    while leftmark <= rightmark and alist[leftmark] <= pivotvalue: 
    leftmark = leftmark + 1 

    while alist[rightmark] >= pivotvalue and rightmark >= leftmark: 
    rightmark = rightmark -1 

    if rightmark < leftmark: 
     done = True 
    else: 
     temp = alist[leftmark] 
     alist[leftmark] = alist[rightmark] 
     alist[rightmark] = temp 

temp = alist[first] 
alist[first] = alist[rightmark] 
alist[rightmark] = temp 

return rightmark 

# alist = [54,26,93,17,77,31,44,55,20] 
# quickSort(alist) 
# print(alist) 

Answer 1

這是不錯的代碼。

與在適當位置完成的快速排版版本（僅使用一個陣列）相比，由於複製/拼接，您的速度可能會慢一些。

快速排序性能非常依賴於關鍵點的選擇。通過選擇第一個元素，在某些情況下，您的代碼以二次方式運行，例如在對已排序的數組進行排序時。 最爲人熟知的優化是：

• 應用杜克的ninther（你避免那些最壞的情況下幾乎可以肯定）選擇一個更好的支點，例如。
• 當子陣列足夠小時執行插入排序（例如，< 10）。

否則，存在運行速度更快的快速排序幾個變體，如三路快速排序使用本特利-麥克羅伊的sheme或雙樞軸快速排序（用於在Java的原始數組進行排序）。插入加速仍適用於這些。