连接列表和 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 = [] 或其他东西。

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

非常感谢！

Answer 1

first 是一个 int 而 l1 和 l2 是列表，因此如果您创建一个包含单个项目的 [] 列表（first) 然后你可以连接三个列表

self.lst = l1 + [first] + l2

有numerous quicksort algorithms but if we use for example the 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

quicksort 是递归的，所以在连接之前，您应该将 l1 和 l2 传递给 quick（尽管看起来您正在使它成为某种自定义列表样式的方法class，所以你应该创建 class 的 l1 和 l2 实例，然后调用 l1.quick())，return l1 + [first] + l2

Answer 3

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

看来你的quick是一个class的方法。当然，如果您愿意，您可以这样做，但这不是必需的。

连接列表和 int

Concatenate list and int

python

sorting

list

quicksort