在c中对双向链表进行排序
我想在插入元素时按排序顺序保留链表（列表中大约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 problem\n"); } new_node->number = value; /* If the first element */ if (head == NULL) { new_node->next = NULL; head = new_node; } else if (new_node->number number) { new_node->next = head; head = new_node; } else { cur_node = head; found = 0; while (( cur_node != NULL ) && ( found == 0 )) { if( new_node->number 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 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; }
您未正确实现合并排序，该排序基于递归地将列表分为两部分，对它们进行排序并合并结果。 但是在你的代码中，你并没有真正将列表分成两半。
注意在行中：
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来跟踪列表的length ，以便能够将其拆分为2.这是对维基百科中的算法的一个很好的解释。
要在链表中插入元素，它排序的前提条件无济于事！ 没有算法可以提供帮助。
您可能需要考虑元素的另一种结构。 根据您的情况，简单的堆或二进制搜索树可能会很好地为您服务。
如果要将大量元素插入到大型有序链表中，可以对它们进行排序，然后进行非常快速的合并O（N）。
对于在线解决方案（在项目到达时插入项目），平衡二叉树可能是一个不错的选择。 它允许在时间O（Log（N））中插入（以及删除）。
否则，MergeSort可以应用于完整列表。
在这两种情况下，O（N.Log（N））总计比较。
链表必须要求O（N）步骤移动到列表中的任意位置。 所以，听起来它不是适合您的数据结构。
您可以尝试在C＃中使用排序集 – std :: set或在C＃中使用SortedSet <>。
如果排序集抽象不适合您的问题，可能最简单的数据结构类似于排序链表是跳过列表： 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 problem\n"); } 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; }