在插入元素（列表中大约有200000个元素）时，我想按排序顺序保持链表，您可以推荐哪种算法？我使用插入排序做了一个简单的实现，但它的性能非常糟糕（占用了大量CPU）。
谢谢你的帮助。
我在合并排序和插入排序之间做了一些比较，但插入排序似乎有更好的性能，我对这个结果有点困惑。你能告诉我哪里出了问题吗？是否有更好的算法？
我的代码（为了简单起见，我省略了节点结构中的prev节点）：
struct node {
int number;
struct node *next;
};
插入排序：
void insert_node(int value) {
struct node *new_node = NULL;
struct node *cur_node = NULL;
struct node *last_node = NULL;
int found; /* 1 means found a place to insert the new node in, 0 means not*/
new_node = (struct node *)malloc(sizeof(struct node *));
if(new_node == NULL) {
printf("memory problemn");
}
new_node->number = value;
/* If the first element */
if (head == NULL) {
new_node->next = NULL;
head = new_node;
}
else if (new_node->number < head->number) {
new_node->next = head;
head = new_node;
}
else {
cur_node = head;
found = 0;
while (( cur_node != NULL ) && ( found == 0 )) {
if( new_node->number < cur_node->number )
{
found = 1;
}
else
{
last_node = cur_node;
cur_node = cur_node->next;
}
}
/* We got the right place to insert our node */
if( found == 1 )
{
new_node->next = cur_node;
}
/* Insert at the tail of the list */
else
{
last_node->next = new_node;
new_node->next = NULL;
}
}
合并排序：
/* add a node to the linked list */
struct node *addnode(int number, struct node *next) {
struct node *tnode;
tnode = (struct node*)malloc(sizeof(*tnode));
if(tnode != NULL) {
tnode->number = number;
tnode->next = next;
}
return tnode;
}
/* perform merge sort on the linked list */
struct node *merge_sort(struct node *head) {
struct node *head_one;
struct node *head_two;
if((head == NULL) || (head->next == NULL))
return head;
head_one = head;
head_two = head->next;
while((head_two != NULL) && (head_two->next != NULL)) {
head = head->next;
head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;
return merge(merge_sort(head_one), merge_sort(head_two));
}
/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) {
struct node *head_three;
if(head_one == NULL)
return head_two;
if(head_two == NULL)
return head_one;
if(head_one->number < head_two->number) {
head_three = head_one;
head_three->next = merge(head_one->next, head_two);
} else {
head_three = head_two;
head_three->next = merge(head_one, head_two->next);
}
return head_three;
}
要在链表中插入元素，对其进行排序的前提条件没有帮助！没有算法可以帮助。
您可能需要为元素考虑其他结构。根据您的情况，一个简单的堆或二进制搜索树可能对您很有用。
如果你想在一个大的排序链表中插入很多元素，你可以对它们进行排序，然后快速合并O（N）。
对于在线解决方案（在项目到达时插入），平衡的二进制树可能是一个不错的选择。它允许在时间O（Log（N））中插入（也允许删除）。
否则，MergeSort可以应用于完整列表。
在这两种情况下，总共进行了O（N.Log（N））比较。
您没有正确实现合并排序，该排序基于递归地将列表分为两部分，对它们进行排序并合并结果。但在您的代码中，您并没有真正将列表一分为二。
注意行中：
while((head_two != NULL) && (head_two->next != NULL)) {
head = head->next;
head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;
当head_two到达列表末尾时退出while循环：例如，如果在循环中到达head_two->next == NULL，则使用head->next->next == NULL退出循环。当你运行head_two = head->next;时，你会得到一个head_two，这样head_two->next == NULL就是列表中的最后一项。
这意味着你基本上是在进行插入排序，而不是合并排序
因此，通过在函数merge_sort中添加参数length，可以将其拆分为2，来跟踪列表的长度。以下是对维基百科中算法的一个很好的解释。
链表必须需要O（N）步才能移动到列表中的任意位置。所以，听起来它不是适合你的数据结构。
您可以尝试在C++或SortedSet<>中使用排序集-std:：set在C#中。
如果排序集抽象不适合您的问题，那么类似于排序链表的最简单的数据结构可能是跳过列表：http://igoro.com/archive/skip-lists-are-fascinating/.更复杂的替代方案是AVL树和红黑树。
优先级队列（特别是跳过列表）是您要查找的。它们允许对数插入，而不是简单链表的O（n）。
下面是在GitHub上用C语言实现的一个跳过列表。
如果您需要将m元素插入到大小为n的排序列表中，您可以直接插入复杂度为m·n的元素，也可以对元素进行预排序（我建议对其进行合并排序），并将它们合并到原始列表中，该列表具有复杂度m·ln(m) + (n + m)。
基本上，您将使用插入和合并排序的专用版本，这两种版本都可以作为在线算法实现，因此非常适合链表。请记住，合并排序的"教科书式"实现效果不佳，因为它在将列表划分为子列表时不必要地迭代列表：您需要稍微复杂一点的基于堆栈的版本。。。
实际上您不想对列表进行排序。合并排序用于对未排序的列表进行排序。（这里有些人已经指出了这一点）。
为了保持列表的排序，你必须在正确的位置插入每个元素。所以基本上你必须：
- 搜索插入新条目的位置
- 插入
这里的复杂性在于搜索算法。
因此，二叉树，甚至更好的是AVL树(http://en.wikipedia.org/wiki/AVL_tree)将非常有效。
另一种选择是使用二进制搜索(http://en.wikipedia.org/wiki/Binary_search_algorithm)。但同样，这只对跳过列表有效。
因此，无论是更改数据结构，还是使用简单的双链表，O（N）复杂性都是最好的。
我喜欢这样的东西的堆。插入和查找是O（log（n）），遍历是O（n）。"heapness"属性可确保始终对数据进行排序。您可以向前和向后遍历，这样您就可以获得双链表的优势。
我已经对您的代码进行了必要的更改。我已经测试过了，效果非常好。您现在应该可以关闭查询了。
struct node *insert_node( struct node *head, int *value )
{
struct node *new_node = NULL;
struct node *cur_node = NULL;
struct node *last_node = NULL;
int found; /* 1 means found a place to insert the new node in, 0 means not*/
new_node = (struct node *)malloc(sizeof(struct node *));
if(new_node == NULL)
{
printf("memory problemn");
}
new_node->number = *value;
/* If the first element */
if (head == NULL)
{
new_node->prev = new_node->next = NULL;
head = new_node;
}
else if (new_node->number < head->number)
{
new_node->next = head;
head = new_node;
}
else
{
cur_node = head;
found = 0;
while (( cur_node != NULL ) && ( found == 0 ))
{
if( new_node->number < cur_node->number )
found = 1;
else
{
last_node = cur_node;
cur_node = cur_node->next;
}
}
/* We got the right place to insert our node */
if( found == 1 )
{
new_node->next = cur_node;
new_node->prev = last_node;
last_node->next = new_node;
cur_node->prev = new_node;
}
/* Insert at the tail of the list */
else
{
last_node->next = new_node;
new_node->next = NULL;
new_node->prev = last_node;
}
}
return head;
}