将项插入链表后进行排序

Question

我有一个c++程序来插入节点到链表。节点包括一个字符串，我们称之为data，和一个指向下一个节点的指针，我们称之为next。此外，头部节点将被定义为head。

我不确定哪个更有效1. 在列表中插入一串字符串，然后排序2. 或者在插入时对列表排序。

我认为是后者，我想知道我将如何去实现这样的东西。

我想知道实现这样一个函数的最简单的方法

Answer 1

第一个解决方案:插入k个未排序的元素，只是将它们插入到开始，每个是O(1)。还有一个排序，在这k个元素之后的O(nlogn)。你得到O(nlogn+k)/k = O(n(logn/k))的平摊时间

第二个解决方案:将一个元素插入到列表中是按O(n)排序的，因为你需要找到列表中的位置。对于k次插入，它将是O(n*k)，并将O(n*k/k) = O(n)平摊。

所以第一个解决方案更适合logn < k，第二个解决方案更适合logn > k

为了提高效率，您可能需要一个以O(logn)访问元素的排序数据结构，例如跳表[它基本上是链表的一种变体，带有更容易访问的附加信息]或avl树

Answer 2

我曾经回答过一个类似的问题(99%相似:))这里

现在我猜它是整数，对于字符串，你可以使用std::string compare函数或C库提供的strcmp进行比较

根据我的意见和看到其他答案，它会更好地为您的应用程序(如果它需要排序链表)排序的数据，因为你插入。

Answer 3

我认为你怎么做其实没有什么区别，当你在插入的时候排序，你会有O(n)的插入时间，因为你可能要遍历整个列表才能找到正确的插入位置。

然而，当您将所有项添加到列表后进行排序时，您还将至少有O(n)个时间在列表中移动项。

Answer 4

最简单的解决方案是使用c++已经提供的std::list和std::list::sort:

#include <list>
#include <algorithm>
#include <iostream>
#include <string>
class Node {
public:
    Node(const std::string& data) : Data(data) {
    }
    std::string Data;
};
bool NodeLess(const Node& n1, const Node& n2) {
    return n1.Data < n2.Data;
}
void main() {
    std::list<Node> l;
    l.push_back(Node("d"));
    l.push_back(Node("c"));
    l.push_back(Node("a"));
    l.push_back(Node("b"));
    l.sort(NodeLess);
    for (auto i = l.begin(); i != l.end(); ++i)
        std::cout << i->Data.c_str() << " ";
}

如果您可以使用它(内存方面)，您还可以使用std::vector在将项目插入链表之前对它们进行预排序(通过std::sort)，这可能会更快一些。

你也可以使用std::map(甚至std::set)来代替list -它会在你插入项目时"自动排序"。

如果你仍然想使用你自己的列表，你可以在其中实现begin和end，并使用std::stable_sort。注意std::stable_sort需要双向迭代器，(不像std::sort需要随机访问迭代器)。要在列表中实现双向迭代器，你需要使它具有双链接，而不仅仅是单链接。

如果你想实现排序本身，可以在链表上实现快速排序和归并排序。