快速排序實現

Question

我想寫到位功能 這裏快速排序是我的代碼

def quick_sort(ar): 
    if len(ar) < 2: 
     return ar 
    pivot = ar[-1] 
    i = 0 

    for j in range(len(ar)): 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[-1] = ar[-1], ar[i] 

    quick_sort(ar[0:i]) 
    quick_sort(ar[i+1:]) 

    return ar 


lst = [1, 3, 9, 8, 2, 7, 5] 
print quick_sort(lst) 

，但我得到的回報一個空列表..什麼，我在這裏失蹤？

Answer 1

您的遞歸調用正在對您的列表進行切片。切片製作副本，所以遞歸完全不會改變原始列表。您需要使用遞歸調用的返回值，否則您應該在原地進行所有操作。每個那些需要對代碼的一些變化，只是在不同的地方

這裏有一個版本的代碼，即構建一個新的列表：

def quick_sort(ar): 
    if len(ar) < 2: 
     return ar 
    pivot = ar[-1] 
    i = 0 

    for j in range(len(ar)): 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[-1] = ar[-1], ar[i] 

    result = quick_sort(ar[0:i]) # build a new result list from the recursive calls 
    result.append(pivot) 
    result.extend(quick_sort(ar[i+1:])) 

    return result 

而這裏的一個排序就地：

def quick_sort(ar, low=0, high=None): # get sorting bounds as arguments 
    if high is None: 
     high = len(ar) 
    if high - low < 2: 
     return 
    pivot = ar[high-1] 
    i = low 

    for j in range(low, high): # iterate on a limited range 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[high-1] = ar[high-1], ar[i] 

    quick_sort(ar, low, i) 
    quick_sort(ar, i+1, high) 

    # no need to return anything, since we sorted ar in place 

鑑於您如何進行分區，就地版本可能更有意義。如果配合使用穩定排序的分區方案（沒有簡便的方法可以實現穩定的快速排序），則其他版本會更有趣。