具有链接列表的mergesort的复杂性 [英] complexity of mergesort with linked list

问题描述

我有使用链表进行mergesort的代码，它工作正常，我的问题是该算法的复杂性是什么?它是O(nlog(n))还是稳定的?我很感兴趣，因为我知道mergesort是稳定的，如何使用链表?如果我们有彼此相等的元素，此代码是否保留了元素的顺序?非常感谢

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 \n");
    for (current=head;current!=NULL;current=current->next)
        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->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).

通常，这就是所谓的 top-down mergesort.您还可以通过 bottom-up 的方式进行操作，方法是首先对两个元素的连续块进行排序，然后将它们合并为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.

要获得额外的效果(并且高效)，请先将列表分为单调的 runs ，而不是从2块开始，即增加序列，并减少序列-重新链接后者您可以按照相反的顺序进行排序-从而根据其固有顺序对原始列表进行细分，因此合并的初始块可能会更少；然后像以前一样重复进行成对合并，直到最后只剩下一个.

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.

这篇关于具有链接列表的mergesort的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！