mergesort与链表的复杂性

我有使用链表的mergesort代码，它运行正常，我的问题是什么是这个算法的复杂性？是O（nlog（n））？还稳定吗？我感兴趣因为我知道mergesort是稳定的，怎么样使用链表？如果我们的元素彼此相等，这段代码是否保留了元素的顺序？非常感谢

#include #include  struct node { int number; struct node *next; }; struct node *addnode(int number,struct node *next); struct node*mergesort(struct node *head); struct node *merge(struct node *one,struct node *two); int main(void){ struct node *head; struct node *current; struct node *next; int test[]={8,3,1,4,2,5,7,0,11,14,6}; int n=sizeof(test)/sizeof(test[0]); int i; head=NULL; for (i=0;inext) printf("%4d\t%4d\n",test[i++],current->number); /* free list */ for (current=head;current!=NULL;current=current->next) next=current->next;free(current); return 0; } 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; } struct node *mergesort(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(mergesort(head_one),mergesort(head_two)); } 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->numbernumber){ 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; } 

Answer 1

你的代码中有一个拼写错误。 通过更正，它确实稳定，并且具有O(n log n)复杂度。 虽然可以肯定，你真的应该重新实现你的merge作为循环而不是递归。 C没有尾调用优化（对吗？），所以这可能会搞乱那里：

 struct node *mergesort(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; // -- the typo, corrected: head_two=head_two->next->next; } head_two=head->next; head->next=NULL; return merge(mergesort(head_one),mergesort(head_two)); } 

在我们处理它的同时， 改变您的工作流程

  return merge(mergesort(head_one),mergesort(head_two)); 

至

  struct node *p1, *p2; // ...... p1 = mergesort(head_one); p2 = mergesort(head_two); return merge(p1,p2); 

这种方式在堆栈上会更容易（将使用更少）。

一般来说，这就是所谓的自上而下的 mergesort。 您也可以自下而上的方式，通过最初排序两个元素的连续块，然后将它们合并到（因此，现在，排序）4个元素的块，然后将这些成对合并为8个元素的块，等，直到只留下一个块 – 排序列表。

要获得额外的花哨（和有效），而不是从2块开始，首先将列表拆分为单调运行 ，即增加序列，减少序列 – 随后重新链接后者 – 从而分割原始列表根据其固有顺序，因此合并的初始块可能会更少; 然后如前所述，重复合并这些成对 ，直到最后只留下一个。

Answer 2

如何不为链表实现mergesort

• 不要递归地将列表一分为二 – 随机访问不是免费的
• 如ruakh所解释的那样，不要划分为1和n - 1子列表

如何实现链接列表的mergesort

而不是使用二分法，通过维护一堆已经排序的子列表来构建列表。 也就是说，首先将大小为1列表推送到堆栈并合并，直到达到更大的列表; 如果你能算出背后的数学，你实际上并不需要存储列表大小。

如果合并函数是，则排序算法将是稳定的。 稳定版本将从头开始构建合并列表，始终从列表中获取单个元素，并在相等的情况下使用第一个列表。 一个不稳定但性能更好的版本会以块的forms添加到合并列表中，从而避免在每个元素之后进行不必要的重新链接。

Answer 3

Mergesort意味着拆分和合并。 下面片段中的分裂并不完美（它导致在均匀分布的游程长度上的二次行为，请参阅Christoph的评论）），但它可以解决这个问题：

 #include  #include  struct llist { struct llist *next; char *payload; }; int llist_cmp(struct llist *l, struct llist *r); struct llist * llist_split(struct llist **hnd , int (*cmp)(struct llist *l, struct llist *r) ); struct llist * llist_merge(struct llist *one, struct llist *two , int (*cmp)(struct llist *l, struct llist *r) ); struct llist * llist_sort(struct llist *ptr , int (*cmp)(struct llist *l, struct llist *r) ); struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) ) { struct llist *this, *save, **tail; for (save=NULL, tail = &save; this = *hnd; ) { if (! this->next) break; if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; } *tail = this->next; this->next = this->next->next; tail = &(*tail)->next; *tail = NULL; } return save; } struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) ) { struct llist *result, **tail; for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) { if (cmp(one,two) <=0) { *tail = one; one=one->next; } else { *tail = two; two=two->next; } } *tail = one ? one: two; return result; } struct llist * llist_sort(struct llist *ptr, int (*cmp)(struct llist *l, struct llist *r) ) { struct llist *save; save=llist_split(&ptr, cmp); if (!save) return ptr; save = llist_sort(save, cmp); return llist_merge(ptr, save, cmp); } int llist_cmp(struct llist *l, struct llist *r) { if (!l) return 1; if (!r) return -1; return strcmp(l->payload,r->payload); } struct llist lists[] = {{ lists+1, "one" } ,{ lists+2, "two" } ,{ lists+3, "three" } ,{ lists+4, "four" } ,{ lists+5, "five" } ,{ lists+6, "six" } ,{ lists+7, "seven" } ,{ lists+8, "eight" } ,{ lists+9, "nine" } ,{ NULL, "ten" } }; int main() { struct llist *root,*tmp; root = lists; fprintf(stdout, "## %s\n", "initial:" ); for (tmp=root; tmp; tmp=tmp->next) { fprintf(stdout, "%s\n", tmp->payload); } fprintf(stdout, "## %s\n", "sorting..." ); root = llist_sort(root, llist_cmp); for (tmp=root; tmp; tmp=tmp->next) { fprintf(stdout, "%s\n", tmp->payload); } fprintf(stdout, "## %s\n", "done." ); return 0; }