链表归并排序的复杂性 [英] complexity of mergesort with linked list
问题描述
我有使用链表进行归并排序的代码,它工作正常,我的问题是这个算法的复杂度是多少?它是 O(nlog(n)) 吗?它是否稳定?我很感兴趣,因为我知道归并排序是稳定的,使用链表怎么样?如果我们有一些彼此相等的元素,这段代码是否保留了元素的顺序?非常感谢
i have code for mergesort using linked list,it works fine,my question what is complexity of this algorithm?is it O(nlog(n))?also is it stable?i am interested because as i know mergesort is stable,what about using linked list?if we have elements with some equal with each-other,does this code preserve orders of elements?thanks a lot
#include<stdio.h>
#include <stdlib.h>
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;i<n;i++)
head=addnode(test[i],head);
i=0;
head=mergesort(head);
printf("before----after sort
");
for (current=head;current!=NULL;current=current->next)
printf("%4d %4d
",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->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 log n)
复杂度.虽然可以肯定的是,您确实应该重新实现您的merge
作为循环而不是递归.C 没有尾调用优化(对吧?),所以这可能会把事情搞砸:
You've got a typo in your code. With it corrected, it is indeed stable, and of O(n log n)
complexity. Although to be sure, you really should reimplement your merge
as a loop instead of recursion. C doesn't have tail call optimization (right?), so this can mess things up there:
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));
}
当我们在做的时候,改变你的工作流程
And while we're at it, change your workflow from
return merge(mergesort(head_one),mergesort(head_two));
到
struct node *p1, *p2;
// ......
p1 = mergesort(head_one);
p2 = mergesort(head_two);
return merge(p1,p2);
以这种方式在堆栈上会容易得多(使用的会少得多).
it'll be much easier on the stack this way (will use much less of it).
一般来说,这就是所谓的自顶向下归并排序.您也可以以自下而上的方式进行,首先对两个元素的连续块进行排序,然后将它们合并为(因此,现在已排序)4个元素的块,然后合并那些成对地,分成8个元素的块,等等,直到只剩下一个块——排序列表.
In general, this here is what's known as top-down mergesort. You could also do it in a bottom-up fashion, by initially sorting the consecutive chunks of two elements each, then merging them into (thus, now, sorted) chunks of 4 elements, then merging those pairwise, into chunks of 8 elements, etc., until only one chunk is left - the sorted list.
为了获得额外的幻想(和效率),而不是从 2 块开始,首先将列表分成单调的 runs,即递增序列和递减序列 - 重新链接后者随着你的前进而反向 - 因此根据其固有顺序对原始列表进行分割,因此可能会合并较少的初始块;然后像以前一样重复合并那些成对,直到最后只剩下一个.
To get extra fancy (and efficient), instead of starting with the 2-chunks, start by splitting the list into monotonic runs, i.e. increasing sequences, and decreasing sequences - re-linking the latter ones in reverse as you go - thus segmenting the original list according to its innate order, so it's likely there will be fewer initial chunks to merge; then proceed merging those pairwise repeatedly, as before, until only one is left in the end.
这篇关于链表归并排序的复杂性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!