Список конкатенации и int

Question

Я пытаюсь изучить python прямо сейчас, и я столкнулся с алгоритмом быстрой сортировки. Это то, что я написал до сих пор с примером списка: [3,1,2,2,1,3,6,7,5,4,8]

def quick(self): 
    first = self.lst[0] 
    l1 = [] 
    l2 = [] 
    for item in self.lst[1:]: 
     if item <= first: 
      l1.append(item) 
      print('this is l1:',l1) 
     else: 
      l2.append(item) 
      print('this is l2:', l2) 

     return _____ 

Я пытаюсь сделать self.lst = l1 + first + l2, однако, когда я делаю это я получаю сообщение об ошибке, которое утверждает:

self.lst = l1 + first + l2 
builtins.TypeError: can only concatenate list (not "int") to list 

I я просто пытаюсь получить первый проход правильно и, возможно, реализовать while True until l1 = [] или что-то в этом роде.

1. Как объединить l1, first и l2 вместе?
2. Что вы, ребята, рекомендуете мне сделать после первого шага?

спасибо!

Answer 1

first является int в то время как l1 и l2 списки, так что если вы создаете список с [] содержащий один элемент (first), то вы можете сцепить три списка

self.lst = l1 + [first] + l2 

Там находятся numerous quicksort algorithms, но если мы использовать, например, Lomuto partition scheme реализация псевдокод на Википедии

algorithm quicksort(A, lo, hi) is 
    if lo < hi then 
     p := partition(A, lo, hi) 
     quicksort(A, lo, p - 1) 
     quicksort(A, p + 1, hi) 

algorithm partition(A, lo, hi) is 
    pivot := A[hi] 
    i := lo  // place for swapping 
    for j := lo to hi - 1 do 
     if A[j] ≤ pivot then 
      swap A[i] with A[j] 
      i := i + 1 
    swap A[i] with A[hi] 
    return i 

В Python это будет выглядеть как

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

def partition(A, lo, hi): 
    pivot = A[hi] 
    i = lo 
    for j in range(lo, hi): 
     if A[j] <= pivot: 
      A[i], A[j] = A[j], A[i] 
      i += 1 
    A[i], A[hi] = A[hi], A[i] 
    return i 

тестирования эта реализация

>>> lst = [3,1,2,2,1,3,6,7,5,4,8] 
>>> quicksort(lst, 0, len(lst)-1) 
>>> lst 
[1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8] 

Answer 2

быстрой сортировки рекурсивно, так перед тем вы конкатенации, вы должны пройти l1 и l2, чтобы быстро (хотя это выглядит, как вы 'сделав его методом какого-то пользовательского класса в стиле списка, поэтому вы должны сделать l1 и l2 экземпляров этого класса, затем вызовите l1.quick()), return l1 + [first] + l2

Answer 3

Cory has обратился к вашему первому вопросу. Что касается второго, вам нужно проверить, что в списке есть хотя бы один элемент, прежде чем вы начнете его разделять. И как только он будет разбит на разделы, вам необходимо перезаписать каждый из l1 и l2. Перед тем, как вы их соедините, вам нужно отсортировать список этих списков.

Похоже, что ваш quick - это метод класса. Конечно, вы может сделать это если хотите, но не требуется.