std :: list.sort（）

Question

奇怪的效率好吧，所以下面：

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

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

欲了解更多信息：在我排序~500个元素的时刻。

我在做错了什么名单？

编辑：一些代码

代码为的std ::列表

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）的时间复杂度。插入每个元素（您可以调用addNoden次），并且您需要n操作来查找插入点（给出n * n = n^2）。

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

你手写的排序是insertion sort的变种。

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

---

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