连接列表和整数

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. 在完成第一步之后，你们建议我做什么？

非常感谢！

- mathn00b

Answer 1

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

- Cory Kramer

Answer 2

快速排序是递归的，所以在连接之前，您应该将l1和l2传递给quick（尽管看起来您正在将其作为某个自定义列表样式类的方法，因此您应该使l1和l2成为该类的实例，然后调用l1.quick()），返回l1 + [first] + l2

- Him

Answer 3

Cory已经回答了你的第一个问题。至于你的第二个问题，你需要在开始对列表进行分区之前检查该列表是否至少有一个元素。一旦它被分区，那么你需要对l1和l2中的每一个进行递归。你需要在连接它们之前将这些子列表排序。

看起来你的quick是一个类的方法。当然，如果你愿意，你可以这样做，但这并不是必要的。

- PM 2Ring