Быстрая реализация Сортировка в питона

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 

Учитывая, как вы занимаетесь секционированием, версия на месте, вероятно, имеет больше смысла. Другая версия была бы более интересной, если бы она сочеталась с схемой секционирования, которая делала ее стабильной (нет простого способа сделать стабильную быструю сортировку на месте).