我可以同时构建和排序一个列表吗？
我正在为一款软件编写脚本，但它并不直接提供我需要的数据。我需要逐个请求所需的信息，并建立一个数据列表。由于各种原因，我需要这个列表是有序的。虽然我可以先建立列表，然后再对其进行排序，这样做很简单，但我觉得一次性处理所有数据可能会更快，而不是先建立列表再排序。
目前，我的代码大致是这样的：
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需要包含这个可迭代对象中的数据。通过这种方式，我先查询出第一个列表，然后遍历它提取数据并放入my_list中。接着，我对这个列表进行排序。最后，我用do_stuff()方法对它进行处理，这个方法会遍历列表，对每个项目进行操作。
问题是，在排序之前我不能对它使用do_stuff()，因为列表的顺序对我来说很重要。我觉得我可能无法避免要遍历列表两次——一次是建立列表，另一次是对每个项目进行操作。因为我们无法提前知道最近添加的项目在添加下一个项目后是否会保持在原来的位置——但我觉得如果能以有序的方式插入每个项目，而不是简单地把它们加到最后，代码会更整洁。就像这样：
for item in "query for stuff":
my_list.append_sorted(item)
这样做值得尝试吗，还是我应该坚持先建立列表，然后再排序呢？
谢谢！
3 个回答
看看这个 bisect 模块。它提供了很多工具来帮助你保持列表的顺序。在你的情况下，你可能想用 bisect.insort。
for item in query_for_stuff():
bisect.insort( my_list, "query for %s data" % item )
这两种方法在大致上是等效的。
排序的时间复杂度是 O(n lg n)（在 Python 中，默认使用 Timsort 排序，只有在数组非常小的时候才会有例外），而在一个已排序的列表中插入元素的时间复杂度是 O(lg n)（使用二分查找），而这个操作你需要做 n 次。
在实际操作中，哪种方法更快可能会有所不同，这取决于你的数据中有多少部分已经是排好序的。
编辑：我之前假设在找到插入点后，在已排序的列表中间插入元素是常数时间（也就是说，列表像链表那样工作，这正是你会用来实现这种算法的数据结构）。但正如 Sven 指出的，这在 Python 列表中可能并不是这样。这会导致“保持列表有序”的方法的时间复杂度变成 O(n^2)，也就是插入排序。
我说“可能”是因为某些列表的实现会随着列表的增长从数组切换到链表，最著名的例子是 CoreFoundation/Cocoa 中的 CFArray/NSArray。这在 Python 中可能是这样，也可能不是。