有序链表

Question

我想建立一个有序的链接列表。

如果我在插入项目时对链接列表进行排序(例如，参见下面的method #1 )，还是只插入所有项目，然后对其进行排序会更快呢？

方法#1

Rough pseudo - code:
for each node in the list
    if newNode is greater than current node
       continue;
    else
       insert the node here;

方法#2

Insert all items.
Sort the list at the end (using QuickSort)

Answer 1

这在很大程度上取决于您要插入的数据。如果按大致降序添加节点，那么在插入节点时排序显然会更快，但如果相反，则会更慢。

如果在完成排序时对其进行排序，则还取决于所使用的排序算法。

通常，当涉及排序算法的选择时，您有更多的双链接列表选项。

此外，在某些应用程序中，始终保持列表的排序是切实可行的，这样您就可以随时查询它。如果您总是添加到列表的头部(或尾部)，那么每次添加内容时都必须重新排序。

您可能还需要考虑其他一些结构，比如保持排序的二叉树，添加/查找节点的时间与树的大小成对数关系，而不是线性地(比如链表)。

Answer 2

理论上他们是一样的。

如果您首先选择(添加时放置正确的空间)来查找合适的索引，则使用二进制搜索将花费O(log )。考虑插入n个元素，您将得到O(n log )时间。

在第二个选项中，在插入所有元素O(n)之后，您将使用合并排序或快速排序(这意味着O(n) + O(n log n) = O(n log n) )对数组进行排序。

因此，它们的复杂度相同，但我更喜欢第一个，以避免额外的插入时间成本。