麻烦帮解决一下，可以上机实现的C语言程序，要求用链表实现归并排序

我之前写过一个，不过是C++的……

对C不太熟，怕改错，就把这个给你凑合一下吧……

跟数组的归并排序很像，你应该能看懂

#include <iostream>

struct Node

{

int data;

Node lnext,rnext;

Node()

{

lnext=NULL;

rnext=NULL;

}

Node(int key)

{

lnext=NULL;

rnext=NULL;

data=key;

}

};

Node Merge(Node L,Node R)

{

Node p,q,ans;

ans=NULL;

while (L!=NULL || R!=NULL)

{

if (R==NULL || (L!=NULL && R!=NULL && L->data<R->data))

{

p=L;

L=L->lnext;

}

else

{

p=R;

R=R->lnext;

}

if (ans==NULL) ans=p;

else

{

p->rnext=q;

q->lnext=p;

}

q=p;

}

p=q=NULL;

return ans;

}

Node Merge_Sort(Node head,int size)

{

if (size==1) return head;

else

{

int m,i;

Node p;

m=size/2;

p=head;

for (i=0;i<m;i++) p=p->lnext;

p->rnext->lnext=NULL;

p->rnext=NULL;

head=Merge_Sort(head,m);

p=Merge_Sort(p,size-m);

return Merge(head,p);

}

}

Node head;

int n;

int main()

{

int data;

Node p;

for (head=NULL,n=0;cin>>data && data!=0;n++)

{

Node temp;

temp=new Node(data);

if (head==NULL) head=temp;

else

{

temp->rnext=p;

p->lnext=temp;

}

p=temp;

temp=NULL;

}

head=Merge_Sort(head,n);

for (p=head;p!=NULL;p=p->lnext) cout<<p->data<<endl;

return 0;

}

最近在研究大数据的分治思想，很多场景计算得出的中间结果都是“内部有序，外部无序”，这时候就要用到“归并排序”算法将多个这样的结果集合归并为一个有序的集合。于是就复习了一下“归并排序”。

在大数据场景中，数据量远大于计算机的内存，磁盘和网络的IO又是无法解决的瓶颈，就需要用到分治思想。

比如有1000G的中国2020年某电商平台用户消费总金额数据。数据格式是用户名：消费总金额。所有数据都是无序的。现在有1台磁盘5T/内存8G（程序可用内存约为5G多）的计算机。如何将数据按消费总金额从大到小排序输出？

a 从有序队列中取出第一个元素。

b 将此元素数据写入输出的文件中，并从此元素所属的数组中的下一个元素放入有序队列。

c 重复步骤a，b直到某个数组元素耗尽，从这个数组所属的5G文件中，继续加载25M数据到内存中。

d 重复步骤a，b，c直到所有5G文件的数据全部加载到内存中，并写入到输出文件。

你的Java归并排序程序,我帮你改完了,你看看吧(改动的地方见注释)

import javautilScanner;

class MergeSort{

 /static void change(int n, int m){//这里去掉change函数,因为它实现不了数组元素交换

 int t = n;

 n = m;

 m = t;

 }/

 static void merge(int[] unmerged, int len){

 if(len<=2){

 if(len==2){

 if(unmerged[0]>unmerged[1]){

  int t = unmerged[0];//这里把调用change函数改成数组元素交换

  unmerged[0] = unmerged[1];

  unmerged[1] = t;}

 }else{return;}

 }

 int mid = (int)len/2;

 int[] x = new int[mid];

 if(len%2==1){mid++;}

 int[] y = new int[mid];

 if(len%2==1){mid--;}

 for(int i=0;i<mid;i++){

 x[i] = unmerged[i];

 }

 for(int i=mid;i<len;i++){

 y[i-mid] = unmerged[i];

 }

 merge(x,mid);

 if(len%2==1){mid++;}

 merge(y,mid);

 if(len%2==1){mid--;}

 for(int i=0;i<mid;i++){//这里把i<=mid;改成i<mid;

 if(x[i]>y[i]){int t = x[i];//这里把调用change函数改成数组元素交换

 x[i] = y[i];

 y[i] = t;}

 }

 for(int i=0;i<mid;i++){

 unmerged[i] = x[i];

 }

 for(int i=mid;i<len;i++){

 unmerged[i] = y[i-mid];

 }

 }

 public static void main(String[] args){

 Scanner sc = new Scanner(Systemin);

 int l = scnextInt();

 int[] a = new int[l];

 for(int i=0;i<l;i++){

 a[i] = scnextInt();

 }

 merge(a,l);

 for(int i=0;i<l;i++){

 Systemoutprint(a[i]+" ");

 }

 scclose();

 }

}

运行结果

5

2 1 4 3 5

1 2 3 4 5

以上就是关于麻烦帮解决一下，可以上机实现的C语言程序，要求用链表实现归并排序全部的内容，包括:麻烦帮解决一下，可以上机实现的C语言程序，要求用链表实现归并排序、大数据中的归并排序(Merge Sort)、java归并排序 自写程序求纠错 编译通过运行时数组越界等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！