c-链表合并的复杂性

我有使用链表进行mergesort的代码，它运行良好，我的问题是这个算法的复杂性是什么？它是O（nlog（n））吗？它稳定吗？我很感兴趣，因为我知道mergesort是稳定的，那么使用链表呢？如果我们有一些元素彼此相等，这个代码会保留元素的顺序吗？非常感谢

#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("%4dt%4dn",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没有尾调用优化（对吧？），所以这可能会把事情搞砸：

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);

这样在堆栈上会容易得多（使用量会小得多）。

一般来说，这就是所谓的自上而下合并。您也可以以自下而上的方式进行操作，首先对每个元素的连续块进行排序，然后将它们合并为（因此，现在已排序）4个元素的块，然后将这些成对合并为8个元素的组块，等等，直到只剩下一个组块-排序列表。

为了获得额外的想象力（和效率），不要从2个块开始，首先将列表拆分为单调的运行，即增加序列和减少序列-在进行时反向重新链接后一个序列-从而根据原始列表的固有顺序对其进行分割，因此需要合并的初始块可能会更少；然后像以前一样，重复地成对合并，直到最后只剩下一个。

如何而不是实现链表合并

不要递归地平分列表-随机访问不是免费的

~~不划分为大小为1和n - 1的子列表，正如ruakh所解释的~~

如何实现链表合并

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

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

Mergesort表示拆分&合并下面片段中的分裂并不完美（它会导致在均匀分布的运行长度上的二次行为，请参阅Christoph的评论），但它会成功：

#include <stdio.h>
#include <string.h>
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, "## %sn", "initial:" );
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%sn", tmp->payload);
        }
fprintf(stdout, "## %sn", "sorting..." );
root = llist_sort(root, llist_cmp);
for (tmp=root; tmp; tmp=tmp->next) {
        fprintf(stdout, "%sn", tmp->payload);
        }
fprintf(stdout, "## %sn", "done." );
return 0;
}

Will Ness的回答：

一般来说，这就是所谓的自上而下的合并。

你也可以用自下而上的方式来做，首先对两个元素的连续块进行排序，然后将它们合并成（因此，现在是排序的）4个元素的块，然后将这些元素成对合并成8个元素的组块，等等，直到只剩下一个组块——排序列表。

作为这种算法的一个例子，考虑一下Git在mergesort.c:中使用的算法

它来自Git 2.34（2021年第四季度），优化了用于排序链表的mergesort实现。

请参阅RenéScharfe（rscharfe）提交的提交c90cfc2（2021年10月8日）和提交afc72b5、提交40bc872、提交84edc40、提交f1ed4ce、提交1a5899、提交0ccb75、提交e031e97、提交d536a71、提交2e67010（2021年十月一日）
^{（由Junio C Hamano合并——gitster——于2021年10月18日提交0ef0809）}

mergesort：使用列组堆栈

^{签字人：RenéScharfe}

自下而上的合并排序实现需要跳过很多子列表。

递归版本可以避免这种情况，但需要log2(n)堆栈帧。

解决方案：显式管理不同长度的排序子列表堆栈，以避免快速转发，同时控制内存使用。

虽然这个补丁是独立开发的，但Mono项目在mono/mono/mono/eglib/sort.frag.h中也使用了ranks堆栈。

其想法是为log2(n_max)排序的子列表保留插槽，每2次方一个插槽。
这样的构造可以容纳高达n_max的任何长度的列表
由于存在已知的最大项目数（有效地为SIZE_MAX），我们可以预先分配整个秩堆栈。

我们一个接一个地添加项目，这类似于增加一个二进制数
在检查某个秩的子列表是否存在时，通过跟踪项的数量和其中的检查位来利用它，而不是检查秩堆栈中的NULL，以避免内存访问。

第一个项目可以作为长度为2^0的子列表进入空的第一个槽

第二个需要与前一个子列表合并，结果将作为长度为2^1的子列表放入空的第二个槽中

第三个进入空出的第一个插槽，依此类推。
最后，我们合并所有的子列表以得到结果

新版本仍然执行稳定的排序，确保在compare函数指示相等时将前面看到的项放在第一位
这是通过更喜欢等级更高的子列表中的项目来实现的。

新的合并函数还试图最大限度地减少操作次数
与blame.c::blame_merge()一样，如果函数已经指向正确的项，则它不会设置下一个指针，并且当它到达给定的两个子列表之一的末尾时，它会退出
旧代码无法执行后者，因为它将所有项目都保存在一个列表中。

不过，比较次数保持不变
以下是"；CCD_ 18"；对于与秩堆栈进行比较次数最多的rand分布：
$ t/helper/test-tool mergesort test | awk '
    NR > 1 && $1 != "rand" {next}
    $7 > max[$3] {max[$3] = $7; line[$3] = $0}
    END {for (n in line) print line[n]}
'
distribut mode                    n        m get_next set_next  compare verdict
rand      copy                  100       32      669      420      569 OK
rand      dither               1023       64     9997     5396     8974 OK
rand      dither               1024      512    10007     6159     8983 OK
rand      dither               1025      256    10993     5988     9968 OK
这里与以前的区别：
distribut mode                    n        m get_next set_next  compare
rand      copy                  100       32     -515     -280        0
rand      dither               1023       64    -6376    -4834        0
rand      dither               1024      512    -6377    -4081        0
rand      dither               1025      256    -7461    -5287        0
CCD_ 19和CCD_。
注意：这些赢家与引入非随机模式的补丁中显示的赢家不同，因为在两者之间添加unriffle_skewed模式改变了rand（）值的消耗。

`mergesort`：使用列组堆栈

相关内容

最新更新

热门标签：

c-链表合并的复杂性

mergesort：使用列组堆栈

相关内容

最新更新

热门标签：

`mergesort`：使用列组堆栈