быстрая сортировка без дополнительной памяти (на месте)

использование:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

есть еще одна лаконичная и красивая версия

def qsort(arr): 
     if len(arr) <= 1:
          return arr
     else:
          return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

# this comment is just to improve readability due to horizontal scroll!!!

позвольте мне объяснить вышеуказанные коды для деталей

1. выберите первый элемент массива arr[0] как pivot

   [arr[0]]

2. qsort те элементы массива, которые меньше, чем поворот с List Comprehension

   qsort([x for x in arr[1:] if x<arr[0]])

3. qsort те элементы массива, которые больше, чем pivot с List Comprehension

   qsort([x for x in arr[1:] if x>=arr[0]])

если я ищу "python quicksort implementation" в Google, этот вопрос является первым результатом, который появляется. Я понимаю, что первоначальный вопрос состоял в том, чтобы" помочь исправить код", но уже есть много ответов, которые игнорируют этот запрос: в настоящее время во-вторых большинство проголосовали один ужасающие шутка с веселым комментарием "Вы уволены" и, в общем, многие реализации, которые не находятся на месте (т. е. используют дополнительную память, пропорциональную входному списку размер.) ответ обеспечивает на месте решение, но это для python 2.x. Итак, ниже следует моя интерпретация решения на месте из Розетта Код который будет работать просто отлично для python 3 тоже:

import random

def qsort(l, fst, lst):
    if fst >= lst: return

    i, j = fst, lst
    pivot = l[random.randint(fst, lst)]

    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j - 1
    qsort(l, fst, j)
    qsort(l, i, lst)

и если вы готовы отказаться от свойства на месте, ниже приведена еще одна версия, которая лучше иллюстрирует основные идеи quicksort. Помимо удобочитаемости, его другим преимуществом является то, что он стабильный (равные элементы отображаются в отсортированном списке в том же порядке, что и в несортированном списке). Это свойство стабильности не выполняется с менее голодной по памяти реализацией на месте, представленной выше.

def qsort(l):
    if not l: return l # empty sequence case
    pivot = l[random.choice(range(0, len(l)))]

    head = qsort([elem for elem in l if elem < pivot])
    tail = qsort([elem for elem in l if elem > pivot])
    return head + [elem for elem in l if elem == pivot] + tail

на это уже есть много ответов, но я думаю, что этот подход является наиболее чистой реализацией:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

вы можете, конечно, пропустить хранение всего в переменных и сразу же вернуть их следующим образом:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

Quicksort с Python

в реальной жизни мы всегда должны использовать встроенную сортировку, предоставляемую Python. Однако, понимая quicksort поучительно.

в быстрая сортировка является, по сути, следующее:

1. Выберите точку сводных данных.
2. переместить все точки данных меньше (ниже) точки поворота в положение ниже точки поворота - переместить те, которые больше или равны (выше) точки поворота в положение выше нее.
3. применить алгоритм к областям выше и ниже оси вращения

если данные распределены случайным образом, выбор первой точки данных в качестве точки вращения эквивалентен случайному выбору.

читабельно пример:

во-первых, давайте посмотрим на читаемый пример, который использует комментарии и имена переменных, чтобы указать на промежуточные значения:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

чтобы переформулировать алгоритм и код, показанные здесь - мы перемещаем значения выше оси вправо, а значения ниже оси влево, а затем передаем эти разделы в ту же функцию для дальнейшей сортировки.

Golfed:

это может быть гольф до 88 символов:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

посмотреть как мы туда доберемся, сначала возьмите наш читаемый пример, удалите комментарии и docstrings и найдите pivot на месте:

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

теперь найдите ниже и выше, на месте:

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

теперь, зная, что and возвращает предыдущий элемент, если false, иначе, если это правда, он оценивает и возвращает следующий элемент, у нас есть:

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

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

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

и чтобы свести к нашему примеру, сократите имена функций и переменных до одной буквы и исключите пробелы, которые не требуются.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

обратите внимание, что эта лямбда, как и большинство кода гольф, довольно плохой стиль.

на месте Quicksort, используя схему секционирования Хоара

предыдущая реализация создает много ненужных дополнительных списков. Если мы сможем сделать это на месте, мы избежим пустая трата пространства.

в приведенной ниже реализации используется схема секционирования Hoare, которую вы можете подробнее об этом читайте в Википедии (но мы, по-видимому, удалили до 4 избыточных вычислений в partition() вызов с помощью семантики while-loop вместо do-while и перемещения шагов сужения до конца внешнего цикла while.).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

не уверен, что я проверил его достаточно тщательно:

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

вывод

этот алгоритм часто преподается на курсах информатики и запрашивается на собеседованиях. Это помогает нам думать о рекурсии и разделять и побеждать.

Quicksort не очень практичен в Python, так как наш встроенный timsort алгоритм довольно эффективен, и у нас есть пределы рекурсии. Мы ожидаем, чтобы сортировать списки на месте с list.sort или создать новые сортированные списки с sorted - оба из которых принимают key и reverse аргумент.

функциональный подход:

def qsort(list):
    if len(list) < 2:
        return list

    pivot = list.pop()
    left = filter(lambda x: x <= pivot, list)
    right = filter(lambda x: x > pivot, list)

    return qsort(left) + [pivot] + qsort(right)

функциональное программирование aproach

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

Я думаю, что оба ответа здесь работают нормально для предоставленного списка (который отвечает на исходный вопрос), но будет разрываться, если передается массив, содержащий не уникальные значения. Поэтому для полноты картины я бы просто указал на небольшую ошибку в каждом из них и объяснил, как их исправить.

например, пытаясь отсортировать следующий массив [12,4,5,6,7,3,1,15,1] (обратите внимание, что 1 появляется дважды) с Brionius.. в какой-то момент будет в конечном итоге с меньше массив пустой а то равной массив с парой значений (1,1), которые не могут быть разделены в следующей итерации и len() > 1...следовательно, вы будете в конечном итоге с бесконечным циклом

вы можете исправить это, либо возвращая массив, если меньше пусто или лучше на не вызов сортировки в равном массиве, как в zangw ответ

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)

        # Don't forget to return something!
        return sort(less)+ equal +sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

более причудливое решение также ломается, но по другой причине оно отсутствует возвращение предложение в строке рекурсии, которое в какой-то момент приведет к возврату None и попытке добавить его в список ....

чтобы исправить это, просто добавьте возврат к этой строке

def qsort(arr): 
   if len(arr) <= 1:
      return arr
   else:
      return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])

def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []

def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A

" истинная "реализация на месте [алгоритмы 8.9, 8.11 из книги" проектирование алгоритмов и приложений " Майкла т. Гудрича и Роберто Тамассии]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()

алгоритм имеет 4 простых шага:

1. разделите массив на 3 части: левую, правую и левую, где pivot будет иметь только один элемент. Выберем этот элемент pivot в качестве первого элемента массива
2. добавить элементы к соответствующей части, сравнивая их с поворотным элементом. (объяснение в комментариях)
3. Рекурсировать этот алгоритм, пока все элементы в массиве не будут отсортированы
4. наконец, присоединяйтесь к левой + pivot+right части

код для алгоритма в python:

def my_sort(A):

      p=A[0]                                       #determine pivot element. 
      left=[]                                      #create left array
      right=[]                                     #create right array
      for i in range(1,len(A)):
        #if cur elem is less than pivot, add elem in left array
        if A[i]< p:
          left.append(A[i])         
          #the recurssion will occur only if the left array is atleast half the size of original array
          if len(left)>1 and len(left)>=len(A)//2:          
              left=my_sort(left)                            #recursive call
        elif A[i]>p: 
          right.append(A[i])                                #if elem is greater than pivot, append it to right array
          if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
              right=my_sort(right)
     A=left+[p]+right                                        #append all three part of the array into one and return it
     return A

my_sort([12,4,5,6,7,3,1,15])

выполнить этот алгоритм рекурсивно с левой и правой частях.

Для Версии Python 3.x: функциональный стиль с помощью operator модуль, в первую очередь, для улучшения читабельности.

from operator import ge as greater, lt as lesser

def qsort(L): 
    if len(L) <= 1: return L
    pivot   = L[0]
    sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

    return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

и тестируется как

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])

def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)

раздел - разделить массив на оси, что меньшие элементы перемещаются влево и большие элементы перемещаются вправо или наоборот. Стержень может быть случайный элемент из массива. Чтобы сделать этот алгоритм, нам нужно знать, что такое начальный и конечный индекс массива и где находится пивот. Затем установите два вспомогательных указателя L, R.

Итак, у нас есть массив user[...,начинать.,..,конец.,..]

начальная позиция L и R указатели
[...начните,далее...,конец.,..]
     R L

пока L   1. Если пользователь[опоры] > пользователей[л] после перемещения R к одной и пользователей своп[Р] С пользователей[л]
  2. я один

через некоторое время поменять пользователя [R] с пользователем[pivot]

быстрая сортировка - используйте алгоритм разбиения до тех пор, пока каждая следующая часть разбиения по оси не будет иметь начальный индекс больше или равен конечному индексу.

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)

или если вы предпочитаете один лайнер, который также иллюстрирует эквивалент Python варагов C/C++, лямбда-выражений и выражений if:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

1. Сначала мы объявляем первое значение в массиве, чтобы быть pivot_value и мы также устанавливаем левую и правую метки
2. мы создаем первый цикл while, этот цикл while есть, чтобы сказать процесс раздела для повторного запуска, если он не удовлетворяет необходимое условие
3. затем мы применяем процесс раздела
4. после того, как оба процесса раздела побежал, мы проверяем, чтобы увидеть, если это удовлетворяет соответствующему условию. Если это так, мы отмечаем это как сделано, если бы не мы переключите левое и правое значения и примените его снова
5. после его завершения переключите левое и правое значения и верните split_point

Я прилагаю код ниже! Это quicksort является отличным инструментом обучения из-за расположение значения pivot. Поскольку он находится в постоянном месте, вы можете пройти через него несколько раз и действительно получить представление о том, как все это работает. На практике лучше всего рандомизировать ось, чтобы избежать O (N^2) во время выполнения.

def quicksort10(alist):
    quicksort_helper10(alist, 0, len(alist)-1)

def quicksort_helper10(alist, first, last):
    """  """
    if first < last:
        split_point = partition10(alist, first, last)
        quicksort_helper10(alist, first, split_point - 1)
        quicksort_helper10(alist, split_point + 1, last)

def partition10(alist, first, last):
    done = False
    pivot_value = alist[first]
    leftmark = first + 1
    rightmark = last
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivot_value:
            rightmark = rightmark - 1

        if leftmark > rightmark:
            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

def quick_sort(l):
    if len(l) == 0:
        return l
    pivot = l[0]
    pivots = [x for x in l if x == pivot]
    smaller = quick_sort([x for x in l if x < pivot])
    larger = quick_sort([x for x in l if x > pivot])
    return smaller + pivots + larger

полный пример с печатными переменными на шаге раздела:

def partition(data, p, right):
    print("\n==> Enter partition: p={}, right={}".format(p, right))
    pivot = data[right]
    print("pivot = data[{}] = {}".format(right, pivot))

    i = p - 1  # this is a dangerous line

    for j in range(p, right):
        print("j: {}".format(j))
        if data[j] <= pivot:
            i = i + 1
            print("new i: {}".format(i))
            print("swap: {} <-> {}".format(data[i], data[j]))
            data[i], data[j] = data[j], data[i]

    print("swap2: {} <-> {}".format(data[i + 1], data[right]))
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1


def quick_sort(data, left, right):
    if left < right:
        pivot = partition(data, left, right)
        quick_sort(data, left, pivot - 1)
        quick_sort(data, pivot + 1, right)

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

print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))

еще одна реализация quicksort:

# A = Array 
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index

def swap(A,i1,i2):
  A[i1], A[i2] = A[i2], A[i1]

def partition(A,g,p):
    # O(n) - just one for loop that visits each element once
    for j in range(g,p):
      if A[j] <= A[p]:
        swap(A,j,g)
        g += 1

    swap(A,p,g)
    return g

def _quicksort(A,s,e):
    # Base case - we are sorting an array of size 1
    if s >= e:
      return

    # Partition current array
    p = partition(A,s,e)
    _quicksort(A,s,p-1) # Left side of pivot
    _quicksort(A,p+1,e) # Right side of pivot

# Wrapper function for the recursive one
def quicksort(A):
    _quicksort(A,0,len(A)-1)

A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]

print(A)
quicksort(A)
print(A)

Это версия quicksort с использованием схемы секционирования Hoare и с меньшим количеством свопов и локальных переменных

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

вот простая реализация: -

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

def quick_sort(list):
    if len(list) ==0:
        return []

    return  quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ]  +  quick_sort( filter( lambda item: item > list[0], list))

def quicksort(items):
    if not len(items) > 1:
        return items
    items, pivot = partition(items)
    return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])


def partition(items):
    i = 1
    pivot = 0
    for j in range(1, len(items)):
        if items[j] <= items[pivot]:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i - 1], items[pivot] = items[pivot], items[i - 1]
    return items, i - 1

inlace sort

def qsort(a, b=0, e=None):
    # partitioning
    def part(a, start, end):
        p = start
        for i in xrange(start+1, end):
            if a[i] < a[p]:
                a[i], a[p+1] = a[p+1], a[i]
                a[p+1], a[p] = a[p], a[p+1]
                p += 1
        return p

    if e is None:
        e = len(a)
    if e-b <= 1: return

    p = part(a, b, e)
    qsort(a, b, p)
    qsort(a, p+1, e)

без рекурсии:

deq = collections.deque()
deq.append((b, e))
while len(deq):
    el = deq.pop()
    if el[1] - el[0] > 1:
        p = part(a, el[0], el[1])
        deq.append((el[0], p))
        deq.append((p+1, el[1]))

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

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

это без использования какой-либо встроенной функции.

разделение функции -

def partitn(alist, left, right):  
 i=left  
 j=right  
 mid=(left+right)/2   

pivot=alist[mid]  
while i <= j:  
    while alist[i] < pivot:  
        i=i+1   

    while alist[j] > pivot:  
        j=j-1   

    if i <= j:  
        temp = alist[i]  
        alist[i] = alist[j]  
        alist[j] = temp  
        i = i + 1   
        j = j - 1   

Я буду делать quicksort с помощью библиотеки numpy. Я думаю, что это действительно полезная библиотека. Они уже реализовали метод быстрой сортировки, но вы можете также использовать свой собственный метод.

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort

indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)

temp_array = []

for index in index_list:
    temp_array.append( array[index])

array = temp_array

print array #it will show sorted array