Ответ 1

def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif 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 handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Ответ 2

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

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

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)

Ответ 3

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

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 те элементы массива, которые меньше чем pivot, с 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]])

Ответ 4

Если я буду искать "быструю сортировку python" в Google, этот вопрос будет первым результатом. Я понимаю, что первоначальный вопрос состоял в том, чтобы "помочь исправить код", но есть много ответов, которые не учитывают этот запрос: второй в настоящее время второй голос, ужасный однострочный с веселым комментарием "Вы уволены" и, в общем,, многие реализации, которые не являются на месте (т.е. используют дополнительную память пропорционально размеру списка входных данных). Этот ответ обеспечивает решение на месте, но оно предназначено для python 2.x Итак, ниже следует моя интерпретация решения на месте от Rosetta Code, которое также отлично python 3 для 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)

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

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

Ответ 5

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

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]])

Ответ 6

Быстрый переход с Python

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

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

Алгоритм быстрой сортировки по существу следующий:

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 и найдите опорную точку на месте:

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]]))

Поскольку lambdas возвращает одно нажатие, и мы упростили одно выражение (даже если оно становится более нечитаемым), мы теперь можем использовать лямбда:

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

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

В приведенной ниже реализации используется схема разбиения 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 аргументы.

Ответ 7

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

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)

Ответ 8

функциональное программирование 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]

Ответ 9

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

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

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

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

Решение fancier также ломается, но по другой причине в рекурсивной строке отсутствует предложение return, которое в какой-то момент приведет к возврату 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]])

Ответ 10

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

Итак, у нас есть пользователь массива [..., begin,..., end,...]

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

тогда как L < конец
  1. Если пользователь [pivot] > пользователь [L] переместит R на один и заменит пользователя [R] на пользователя [L]
  2. переместите L на один

После того, как пользователь swap [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)

Ответ 11

Или, если вы предпочитаете однострочный, который также иллюстрирует эквивалент Python C/С++ varags, лямбда-выражений и выражения 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])

Ответ 12

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 []

Ответ 13

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

Ответ 14

"Истинная" реализация на месте [Алгоритмы 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 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()

Ответ 15

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

• Разделите массив на 3 разные части: влево, вправо и вправо, где pivot будет иметь только один элемент. Выберем этот элемент поворота как первый элемент массива
• Добавлять элементы в соответствующую часть, сравнивая их с элементом поворота. (пояснение в комментариях)
• Повторите этот алгоритм до тех пор, пока все элементы массива не будут отсортированы.
• Наконец, присоедините left + pivot + right parts

Код для алгоритма в 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])

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

Ответ 16

Другая реализация быстрой сортировки:

# 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)

Ответ 17

Для версии 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])

Ответ 18

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)

Ответ 19

Это версия 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)

Ответ 20

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

Как это работает?

1. По сути, мы выбираем первый элемент в качестве нашего стержня из нашего списка, а затем создаем два подсписка.
2. Наш первый подсписок содержит элементы, которые меньше, чем пивот
3. Наш второй подсписок содержит наши элементы, которые больше или равны Pivot
4. Затем мы быстро сортируем каждую из них и объединяем первую группу + сводную + вторую группу, чтобы получить окончательный результат.

Вот пример вместе с визуальным сопровождением... (сводка) 9,11,2,0

среднее: n log n

худший случай: n ^ 2

Код:

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

items = [9,11,2,0] print (быстрая сортировка (items))

Ответ 21

Алгоритм содержит две границы, одна из которых имеет элементы меньше, чем точка поворота (отслеживаемая индексом "j"), а другая имеет элементы больше, чем точка поворота (отслеживаемая индексом "i").

На каждой итерации новый элемент обрабатывается путем увеличения j.

Инвариантная: -

1. все элементы между стержнем и я меньше, чем стержень, и
2. все элементы между я и j больше, чем опорная точка.

Если инвариант нарушается, i-й и j-й элементы меняются местами, а я увеличивается.

После того, как все элементы были обработаны, и все после того, как сводка была разделена, элемент сводки заменяется на последний элемент меньше его.

Элемент поворота теперь будет на своем правильном месте в последовательности. Элементы до него будут меньше его, а элементы после него будут больше его, и они будут не отсортированы.

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Выбор оси

"Хороший" поворот приведет к двум подпоследовательностям примерно одинакового размера. Детерминистически, элемент поворота может быть выбран наивным способом или путем вычисления медианы последовательности.

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

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

Недетерминированный/случайный способ выбора оси будет состоять в том, чтобы выбрать элемент случайным образом. Это простой и легкий подход, который минимизирует наихудший сценарий, а также приводит к примерно сбалансированному расколу. Это позволит также обеспечить баланс между наивным подходом и срединным подходом выбором шарнира.

Ответ 22

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

Я прилагаю код ниже! Эта быстрая сортировка - отличный инструмент для обучения из-за местоположения значения поворота. Поскольку он находится в постоянном месте, вы можете пройти через него несколько раз и действительно понять, как все это работает. На практике лучше всего рандомизировать стержень, чтобы избежать времени выполнения 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

Ответ 23

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

Ответ 24

Полный пример с печатными переменными на этапе разделения:

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))

Ответ 25

Здесь простая реализация: -

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]))

Ответ 26

def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don't have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()

Ответ 27

# 编程珠玑实现
# 双向排序: 提高非随机输入的性能
# 不需要额外的空间,在待排序数组本身内部进行排序
# 基准值通过random随机选取
# 入参: 待排序数组, 数组开始索引 0, 数组结束索引 len(array)-1
import random

def swap(arr, l, u):
    arr[l],arr[u] = arr[u],arr[l]
    return arr

def QuickSort_Perl(arr, l, u):
    # 小数组排序i可以用插入或选择排序 
    # if u-l < 50 : return arr
    # 基线条件: low index = upper index; 也就是只有一个值的区间
    if l >= u:
        return arr
    # 随机选取基准值, 并将基准值替换到数组第一个元素        
    swap(arr, l, int(random.uniform(l, u)))
    temp = arr[l]
    # 缓存边界值, 从上下边界同时排序
    i, j = l, u
    while True:
        # 第一个元素是基准值,所以要跳过
        i+=1
        # 在小区间中, 进行排序
        # 从下边界开始寻找大于基准值的索引
        while i <= u and arr[i] <= temp:
            i += 1
        # 从上边界开始寻找小于基准值的索引
        # 因为j肯定大于i, 所以索引值肯定在小区间中
        while arr[j] > temp:
            j -= 1
        # 如果小索引仍小于大索引, 调换二者位置
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    # 将基准值的索引从下边界调换到索引分割点
    swap(arr, l, j)
    QuickSort_Perl(arr, l, j-1)
    QuickSort_Perl(arr, j+1, u)
    return arr

print('QuickSort_Perl([-22, -21, 0, 1, 2, 22])',
    QuickSort_Perl([-22, -21, 0, 1, 2, 22], 0, 5))

Ответ 28

Этот алгоритм не использует рекурсивные функции.

Пусть N будет любым списком чисел с len(N) > 0. Установите K = [N] и выполните следующую программу.

Примечание. Это стабильный алгоритм сортировки.

def BinaryRip2Singletons(K, S):
    K_L = []
    K_P = [ [K[0][0]] ] 
    K_R = []
    for i in range(1, len(K[0])):
        if   K[0][i] < K[0][0]:
            K_L.append(K[0][i])
        elif K[0][i] > K[0][0]:
            K_R.append(K[0][i])
        else:
            K_P.append( [K[0][i]] )
    K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
    while len(K_new) > 0:
        if len(K_new[0]) == 1:
            S.append(K_new[0][0])
            K_new = K_new[1:]
        else: 
            break
    return K_new, S

N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []

print('K =', K,  =', S)
while len(K) > 0:
    K, S = BinaryRip2Singletons(K, S)
    print('K =', K,  =', S)

ПРОГРАММНЫЙ ВЫХОД:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]

Ответ 29

Простая реализация из алгоритмов гроккинга

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

Ответ 30

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))