std::list.sort()的奇怪效率

Question

好的，那么下面的内容:

我想使用一个双链表，并希望对其中的对象进行排序。对象属于另一个类。奇怪的是:当我使用我自己创建的双链表时，我在将元素添加到列表中时对它们进行排序。这就像插入排序，效率是n^2。

但是这比使用std::list排序更快，在std::list排序中，我将所有元素添加到列表中，然后调用sort()。我真的不明白为什么....

进一步的信息:在这一刻，我排序~ 500个元素。

我的列表做错了吗?

编辑:一些代码

std::list 的代码

for every object:
    list.push_back(object);
list.sort();

我的列表:

struct node{
    someObject* data;
    float depth;
    node* prev;
    node* next;
    node(someObject* o){
        data = o;
        prev = NULL;
        next = NULL;
        depth = depthFunc(o);
    }
    float depthFunc(someObject* o);
};
struct myList{
    node* head;
    node* tail;
    void insertAfter(node* toAdd, node* n);
    void insertBefore(node* toAdd, node* n);
    void addNode(someObject* o){
        node* n = new node(o);
        if (head == NULL) {
            head = n;
            tail = n;
        } else {
            node* temp = head;
            while(temp != NULL && temp->depth < n->depth){
                temp = temp->next;
            }
            if (temp != NULL) insertBefore(n, temp);
            else insertAfter(n, tail);
        }
    }
};

Answer 1

您手写的排序函数具有O(N^2)时间复杂度。每个元素被插入(你调用addNode n次)，并且你需要n操作来找到插入点(给出n * n = n^2)。

std::list<T>::sort()要求复杂度为0 (n lg n)，比0 (N^2)快得多。(lg n比n长得慢得多)

你手写的排序是插入排序的一个变体。

请注意，对于大多数输入，使用std::vector和std::sort而不是std::list和std::list::sort会给出更快的结果。

---

如果你的问题是问"为什么手写版本更快?"，这取决于你的输入。对于某些输入，插入排序可以是O(n)。(对于您的实现，当元素以反向顺序插入时，就会发生这种情况)