我可以建立一个列表,并同时对其进行排序吗？

Question

我正在为一个软件编写脚本,它并没有真正让我直接访问我需要的数据.相反,我需要询问我需要的每一条信息,并建立一个我正在获得的数据列表.由于各种原因,我需要对列表进行排序.只需构建一次列表,然后对其进行排序,然后对其进行处理就很容易了.但是,我认为一次运行所有内容会更快,而不是构建列表然后对其进行排序.

所以,目前我基本上得到了这个:

my_list = []

for item in "query for stuff":
    my_list.append("query for %s data" % item)

my_list.sort()

do_stuff(my_list)

"查询东西"位是与软件的查询界面,这将给我一个可迭代的.my_list需要包含来自所述iterable内容的数据列表.通过这样做,我正在查询第一个列表,然后循环它以提取数据并将其放入my_list.然后我正在整理它.最后,我正在使用do_stuff()方法对其进行操作,该方法将遍历它并对每个项目执行操作.

问题是在排序之前我不能do_stuff(),因为列表顺序由于各种原因很重要.我不认为我可以摆脱两次循环列表 - 一次构建列表,一次对其中的每个项目做东西,因为我们事先不知道N位置最近添加的项目是否会在我们添加下一个项目之后保持在位置N - 但是以排序的方式插入每个项目似乎更干净,而不是仅仅在最后添加它们.有点像这样:

for item in "query for stuff":
    my_list.append_sorted(item)

是否值得尝试这样做,或者我应该坚持建立列表,然后对其进行排序？

谢谢!

Answer 1

简短的回答是:它不值得.

看一下插入排序.最坏情况下的运行时间是O(n^2)(平均情况也是二次的).另一方面,Python的排序(也称为Timsort)将采用O(n log n)最坏的情况.

是的,在您插入时保持列表排序"看起来"更清晰,但这是一个谬论.没有真正的好处.您考虑使用插入排序的唯一时间是您需要在每次插入后显示排序列表.

Answer 2

这两种方法渐近等价。

排序的时间复杂度为 O(n lg n)（Python 默认使用 Timsort，除了非常小的数组），在排序列表中插入的时间复杂度为 O(lg n)（使用二分搜索），您必须执行 n 次。

实际上，一种方法或另一种方法可能会稍微快一些，具体取决于已排序的数据量。

编辑：我假设在找到插入点后在排序列表的中间插入将是恒定时间（即列表的行为类似于链接列表，这是您将用于此类算法的数据结构）。正如 Sven 指出的那样，Python 列表的情况可能并非如此。这将使“保持列表排序”方法的复杂度为 O(n^2)，即插入排序。

我说“可能”是因为随着列表的增长，一些列表实现从数组切换到链表，最值得注意的例子是 CoreFoundation/Cocoa 中的 CFArray/NSArray。Python 可能会出现这种情况，也可能不会。