-1

好的，所以以下内容：

我想使用一个双链表并想对其中的对象进行排序。对象属于另一类。奇怪的是：当我使用自己创建的双链表时，我在将元素添加到列表的那一刻对它们进行排序。这就像插入排序，所以效率为 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);
        }
    }
};
4

1 回答 1

2

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

std::list<T>::sort()需要 O( n lg n·) 复杂度，这比 O(·) 快得多N^2。（lg n比增长慢得多n）

您的手写排序是插入排序的变体。

请注意，对于大多数输入，使用std::vectorandstd::sort代替std::listandstd::list::sort会产生更快的结果。

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

于 2013-04-22T23:21:20.210 回答