快速排序实现

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 

鉴于您如何进行分区，就地版本可能更有意义。如果配合使用稳定排序的分区方案（没有简便的方法可以实现稳定的快速排序），则其他版本会更有趣。