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

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