sorting - 有序链表

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)

score 0 · Accepted Answer

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

如果在完成后对其进行排序，它还取决于您使用的排序算法。

一般来说，当涉及到排序算法的选择时，双向链表有更多的选择。

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

您可能还需要考虑其他结构，例如保持自身排序的二叉树以及添加/查找节点的时间与树的大小成对数相关而不是线性相关（如链表）。

score 0 · Accepted Answer

理论上它们是相同的。

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

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

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

2 回答 2