4

我不明白为什么我的列表在 Nonetype 中。我正在尝试构建一个接收 int 列表的函数，该列表的第一个索引是枢轴，然后对列表的其余部分进行排序，因此每个大于枢轴的 int 都将位于右侧，而 int 则小于枢轴将在左侧。int 不需要从小到大排序。这是我的代码：

def divide_list(lst):
    pivot = lst[0]
    lst= lst.reverse()
    for i in lst:
        if i>pivot:
            lst.append(i)
            lst.remove(i)
    return lst

谢谢！

4

4 回答 4

3

lst.reverse()反转列表并返回None. 不要将返回值分配回lst：

def divide_list(lst):
    pivot = lst[0]
    lst.reverse()
    for i in lst:
        if i>pivot:
            lst.append(i)
            lst.remove(i)
    return lst

如果您不想lst就地更改，请使用负切片以相反的顺序获取列表的新副本：

def divide_list(lst):
    pivot = lst[0]
    lst = lst[::-1]
    for i in lst:
        if i>pivot:
            lst.append(i)
            lst.remove(i)
    return lst

这仍然会导致各种问题；for当您在循环中就地更改列表时，您的方法将不起作用。当您向列表添加和删除元素时，迭代器不会更新，列表行为也不会是您所期望的。

假设您有一个[3, 4, 1, 2]反转后的列表，枢轴是2。在循环中，循环使用的迭代器for查看lst[0]，您3可以通过追加和删除移动到列表的末尾。现在列表看起来像[4, 1, 2, 3]，循环前进到lst[1]，所以到1值。4完全被跳过了！

于 2013-11-06T17:42:42.677 回答
1

修改您正在迭代的列表是个坏主意；更大的输入列表也会变慢。最好使用新列表来构建结果。

def divide_list(lst):
    ret = []  # might replace with collections.deque
              # for better performance with larger inputs
    pivot = lst[0]
    for i in reversed(lst):
        if i > pivot:
            ret.append(i)
        else:
            ret.insert(0, i)
    return ret

此外，您可以使用 2 个单独的列表，然后将它们作为元组返回，或者在最后连接它们：

def divide_list(lst):
    left, right = [], []
    pivot = lst[0]
    for i in reversed(lst):
        (right if i > pivot else left).append(i)
    return left + right  # or (left, right)

或者您甚至可以通过使用生成器对列表进行 2 次迭代，但避免代价高昂append或串联操作：

def divide_list(lst):
    pivot = lst[0]
    for i in reversed(lst):
        if i < pivot: yield i
    for i in reversed(lst):
        if i >= pivot: yield i

new_list = list(divide_list(orig_list))
于 2013-11-06T17:50:33.580 回答
0

看起来您正在实施快速排序。如果是这样的话，我可能会做这样的事情：

def divide_list(lst):
    pivot = lst[0]
    left = []
    right = []
    for item in lst:
        if item > pivot:
            right.append(item)
        else:
            left.append(item)
    return left, right

当然，如果你想要一个最后的列表，你可以做一些有趣的事情，比如：

    return left[::-1] + right

反转左，然后将其与右连接。

于 2013-11-06T17:50:49.030 回答
0

其他人已经为您提供了错误的解释，但也许您会考虑更直接的实现？

def divide_list(lst):
    pivot = lst[0]
    return [i for i in lst if i <= pivot] + [i for i in lst if i > pivot]
于 2013-11-06T17:52:55.673 回答