连接列表和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

我只是想让第一遍正确,也许实现一个while True until l1 = []或者什么.

1. 如何将l1,first和l2连接在一起？
2. 在第一步之后,你们建议我做什么？

非常感谢你!

Answer 1

first是一段int时间l1而且l2是列表,所以如果你创建一个[]包含单个项目(first)的列表,那么你可以连接这三个列表

self.lst = l1 + [first] + l2

有许多快速排序算法但是如果我们使用例如Lomuto分区方案,那么维基百科上的伪代码实现就是

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]