二路归并排序代码

『壹』 求java实现二路归并的程序

packagealgorithm;

publicclassMergeSort{
//privatestaticlongsum=0;
/**
*<pre>
*二路归并
*原理：将两个有序表合并和一个有序表
*</pre>
*
*@parama
*@params
*第一个有序表的起始下标
*@paramm
*第二个有序表的起始下标
*@paramt
*第二个有序表的结束小标
*
*/
privatestaticvoidmerge(int[]a,ints,intm,intt){
int[]tmp=newint[t-s+1];
inti=s,j=m,k=0;
while(i<m&&j<=t){
if(a[i]<=a[j]){
tmp[k]=a[i];
k++;
i++;
}else{
tmp[k]=a[j];
j++;
k++;
}
}
while(i<m){
tmp[k]=a[i];
i++;
k++;
}

while(j<=t){
tmp[k]=a[j];
j++;
k++;
}
System.array(tmp,0,a,s,tmp.length);
}

/**
*
*@parama
*@params
*@paramlen
*每次归并的有序集合的长度
*/
publicstaticvoidmergeSort(int[]a,ints,intlen){
intsize=a.length;
intmid=size/(len<<1);
intc=size&((len<<1)-1);
//-------归并到只剩一个有序集合的时候结束算法-------//
if(mid==0)
return;
//------进行一趟归并排序-------//
for(inti=0;i<mid;++i){
s=i*2*len;
merge(a,s,s+len,(len<<1)+s-1);
}
//-------将剩下的数和倒数一个有序集合归并-------//
if(c!=0)
merge(a,size-c-2*len,size-c,size-1);
//-------递归执行下一趟归并排序------//
mergeSort(a,0,2*len);
}

publicstaticvoidmain(String[]args){
int[]a=newint[]{4,3,6,1,2,5};
mergeSort(a,0,1);
for(inti=0;i<a.length;++i){
System.out.print(a[i]+"");
}
}
}

『贰』 C语言，二路归并排序，递归调用到底是怎么调用的求详解！

程序代码都是顺序执行的，当然是把一路调用完再做第二路调用，最后把排好序的2路进行合并；

在排序每一路的时候也是使用归并的方式，把一路分成2路，层层深入。

理解的话，你可以这样：

比如8个数，你从上到下竖着排成一列，然后中间一条横线分割。

横线上面的部分再从中间分割成2部分，2部分放在第二列；

依次往后分割。得到形如这样的图：

然后按照红色箭头先按A反推一层，再按B向下一层，这样就会合并一次产生排好序的前一层。如此反复，这就是递归实际的执行流程。

『叁』 简述二路归并排序,并分析其算法复杂性.

二路归并,就是将两个有序序列,合并为一个有序的序列
而排序最初是一个无序序列,此时就要将其分解为两个有序序列
这里就用到一个递归的思想
即：将该算法截为两段,对前后两段应用该算法均可得到一个有序序列,这是就有了两个有序序列,再使用该算法就最终得到一个有序序列
而递归终点是当分段内只有一个元素时,显然就是有序序列了,就可以返回
具体的代码为：
void Merge(int r[],int r1[],int s,int m,int t)//二路归并
{
int i=s,j=m+1,k = s;
while(i

『肆』 跪求二路归并排序的程序用VB或者VC编写

// 排序法.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

void maopaopaixu(int acount,int a[]);//冒泡排序法
void twowaypaixu(int acount,int a[]);//2路归并排序法
int _tmain(int argc, _TCHAR* argv[])
{
int a[12]={5,5,6,3,4,2,7,8,0,10,1,11};
int b[12]={5,5,6,3,4,2,7,8,0,10,1,11};
maopaopaixu(12,a);
twowaypaixu(12,b);
return 0;
}
void twowaypaixu(int acount,int a[])
{
int p=a[(int)acount/2];
int *b,*c;
b=new int[acount];
c=new int[acount];
int bi=0,ci=0;
int tmp,k=0;
for(int i=0;i<acount;i++)
{
k++;
if(a[i]>p)*(b+bi++)=a[i];else *(c+ci++)=a[i];
}

for(int i=0;i<bi-1;i++)
{
for(int j=i+1;j<bi;j++)
{
k++;
if(*(b+i)<*(b+j))
{
tmp=*(b+i);
*(b+i)=*(b+j);
*(b+j)=tmp;
}
}
}

for(int i=0;i<ci-1;i++)
{
for(int j=i+1;j<ci;j++)
{
k++;
if(*(c+i)<*(c+j))
{
tmp=*(c+i);
*(c+i)=*(c+j);
*(c+j)=tmp;
}
}
}

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

if(i<bi)
std::cout<<*(b+i)<<" ";
else
std::cout<<*(c+i-bi)<<" ";
}
std::cout<<std::endl<<"2路归并法共运算了"<<k<<"次"<<std::endl;
}
void maopaopaixu(int acount,int a[])
{
int tmp,k=0;
for(int i=0;i<acount-1;i++)
{
for(int j=i+1;j<acount;j++)
{
k++;
if(a[i]<a[j])
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
}

for(int i=0;i<acount;i++)
{
std::cout<<a[i]<<" ";
}
std::cout<<std::endl<<"冒泡法共运算了"<<k<<"次"<<std::endl;
}

『伍』 求大神解释下二路归并排序法，C语言。

#include <stdio.h>
#include<malloc.h>
void merge(int *a, int beg, int mid, int end)// 合并子序列
{
int i=beg, j=mid+1, cnt=0;
int *a1;
a1=(int*)malloc((end-beg+1)*sizeof(int));

while(i<=mid && j<=end)
{
a1[cnt++]=a[i]<=a[j]? a[i++]:a[j++];
}
while(i<=mid)
{
a1[cnt++]=a[i++];
}
while(j<=end)
{
a1[cnt++]=a[j++];
}
for(cnt=0, i=beg; i<=end; cnt++,i++)
{
a[i]=a1[cnt];
}

}
void merge_sort(int*a, int beg, int end)//二路归并排序
{
int mid=0;
if(beg<end)
{
mid=(beg+end)/2;//左右两部分分解
merge_sort(a, beg, mid);//左半部分排序
merge_sort(a, mid+1, end);//右半部分排序
merge(a, beg, mid, end);//左右两部分合并
}
}

int main(void)
{
int a[10]={12,54,14,25,21,87,48,1,547,12};

int i=0,j=0,k=0;
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');
merge_sort(a, 0, 9);
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');

}

『陆』 随机生成10个待排序数据，用C语言写出二路归并排序算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int b[ 10 ];void Merge( int c[], int d[], int l, int m, int r )
{
int i = l, j = m + 1, k = l;
while( ( i <= m ) && ( j <= r ) )
if( c[ i ] <= c[ j ] ) d[ k++ ] = c[ i++ ];
else d[ k++ ] = c[ j++ ];
if( i > m )
for( int q = j; q <= r; q++ ) d[ k++ ] = c[ q ];
else
for( int q = i; q <= m; q++ ) d[ k++ ] = c[ q ];
}void Copy( int c[], int d[], int n1, int n2 )
{
for( int i = n1; i <= n2; i++ )
c[ i ] = d[ i ];
}void MergeSort( int a[], int left, int right )
{
if( left < right ) {
int i = ( left + right ) / 2; //取中点，分成两路
MergeSort( a, left, i );
MergeSort( a, i + 1, right );
Merge( a, b, left, i, right ); //合并到数组b
Copy( a, b, left, right ); //复制到数组a
}
}int main()
{
int a[ 10 ], i;
srand( time( 0 ) );
for( i = 0; i < 10; i++ ) a[ i ] = rand() % 100; //随机生成
for( i = 0; i < 10; i++ ) //输出随机生成的数据
printf( "%d\t", a[ i ] );
printf( "\n" );
MergeSort( a, 0, 9 );
for( i = 0; i < 10; i++ ) //输出排序后的结果
printf( "%d\t", a[ i ] );
printf( "\n" );
return 0;
} //在vc++6.0上调试运行成功。若有不明白的地方，call me!!!

『柒』 归并排序代码

MERGE(rectypr R[],rectype R1[],int low,int mid,int
high)
{ int i,j,k;
i=low; j=mid+1; k=low;
while ((i<=mid)&&(j<=high))
if (R[i].key<=R[j].key) R1[k++]=R[i++];
else R1[k++]=R[j++];
while (j<=mid) R1[k++]=R[i++];
while (j<=high) R1[k++]=R[j++];
}

分析：
归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列R[0]到R[n-1]看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。

一趟归并算法
MERGEPASS(rectype R[],rectype R1[],int length)
{ int i,j;
i=0;
while (i+2*length-1<n)
{ MERGE(R,R1,i,i+length-1,i+2*length-1);
i=i+2*length;
}
if (i+length-1<n-1)
MERGE(R,R1,i,i+length-1,n-1);
else
for (j=i;j<n;j++) R1[j]=R[j];
}

算法复杂性分析：
归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。

两路归并的基本思想：
设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键字小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。

『捌』 C语言编程，二路归并排序，希尔排序

#include<iostream>
#include<string>
using namespace std;
int n=20;

class student
{
long int num;//学号
char name[20];//姓名
int grade;
public:
student(){}
student(long nu,char na[],int gr){num=nu;strcpy(name,na);grade=gr;}
void put_student(long nu,char na[],int Chinese,int math,int English){num=nu;strcpy(name,na);grade=Chinese+math+English;}
int get_grade(){return grade; }
void get_student(){cout<<num<<" "<<name<<" "<<grade<<" "<<endl;}
long int get_num(){return num;}
char* get_name(){return name;}
student::operator=(class student a){num=a.num;strcpy(name,a.name);grade=a.grade;}
};
void taxis(class student a[]) //按总成绩由大到小排序
{
class student b;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(a[i].get_grade()<a[j].get_grade())
{
b=a[i];
a[i]=a[j];
a[j]=b;
}
}

void insert(class student a[]) //将一个新学生总成绩插入已排好序数组中
{
long int num;//学号
char name[20];//姓名
int grade;
cout<<"请输入学号,姓名,总分,";
cin>>num>>name>>grade;
class student c(num,name,grade);
for(int i=0;i<n;i++)
{
if(a[i].get_grade()<c.get_grade())
break;
}
n++;
for(int j=n;j>i;j--)
a[j]=a[j-1];
a[j]=c;
}

void del(class student a[]) //将不及格学生记录删除
{
int j=0;
for(int i=0;i<n;i++)
if(a[i].get_grade()>=(60*3))
a[j++]=a[i];
n=j;
}

void save(class student a[]) //排序的结果用文件形式存放磁盘
{
FILE *fp;
if((fp=fopen("save_student.dat","w"))==NULL)
{cout<<"ERROR"<<endl;exit(0);}
for(int i=0;i<n;i++)
{
fprintf(fp,"%-10d%-10s%-5d\n",a[i].get_num(),a[i].get_name(),a[i].get_grade());
}
if(fp!=NULL)
fclose(fp);
}

void main(void)
{
long int num;//学号
char name[20];//姓名
int Chinese,math,English;//3门课成绩
FILE *fp;
class student a[30];
if((fp=fopen("student.dat","r"))==NULL)
{cout<<"ERROR"<<endl;exit(0);}
for(int i=0;i<n;i++)
{
fscanf(fp,"%d%s%d%d%d",&num,&name,&Chinese,&math,&English);
a[i].put_student(num,name,Chinese,math,English);
}
taxis(a);
for(i=0;i<n;i++)
a[i].get_student();
insert(a);
for(i=0;i<n;i++)
a[i].get_student();
cout<<"del(a)"<<endl;
del(a);
for(i=0;i<n;i++)
a[i].get_student();
save(a);
if(fp!=NULL)
fclose(fp);;
}

B.按总成绩由大到小排序（同组采用不同排序方法）
同组 是什么意思..
==
student.dat格式
学号 姓名 3门课成绩
1 Adaam 8 90 50

『玖』 简述二路归并排序，并分析其算法复杂性。

二路归并，就是将两个有序序列，合并为一个有序的序列

而排序最初是一个无序序列，此时就要将其分解为两个有序序列
这里就用到一个递归的思想
即：将该算法截为两段，对前后两段应用该算法均可得到一个有序序列，这是就有了两个有序序列，再使用该算法就最终得到一个有序序列
而递归终点是当分段内只有一个元素时，显然就是有序序列了，就可以返回

具体的代码为：
void Merge(int r[],int r1[],int s,int m,int t)//二路归并
{
int i=s,j=m+1,k = s;
while(i<=m && j<=t)
{
if (r[i] <= r[j]) r1[k++] = r[i++];
else r1[k++] = r[j++];
}
if(i <= m)
{
while(i <= m)
r1[k++] = r[i++];
}
else
{
while (j <= t)
r1[k++] = r[j++];
}
}

void MergeSort(int r[],int r1[],int s,int t)//递归调用
{
if(s == t) r1[s] = r[s];
else{
m = (s + t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}

至于它的时间复杂度，从严格分析上说是O（nlog2n）,我做过测试，它在较大数据排序时，性能不亚于快排，堆排，并且和初始数据顺序性无关，是一种稳定的排序算法
至于缺点就是它的空间复杂度，达到O（n）

此外，它还有非递归算法，思想都是一样的，我就不多说了，如果你需要，可以Hi我

『拾』 二路归并排序，递归，我的这个哪里错了

请参照以下代码:

#include<stdio.h>
staticintcount=0;
staticintn_data=0;
voidMerge(intb[],intp,intc[],intq,inta[])
{
inti=0;
intj=0;
intk=0;
//while(i<p&&j<q)//问题应该出现在这里，应该判断b和c的下标才对吧？
while(j<p&&k<q)
{
if(b[j]<=c[k])
{
a[i++]=b[j++];
}
else
{
a[i++]=c[k++];
}
}
if(j==p)
{
while(k<q)
{
a[i++]=c[k++];
}
}
else
{
while(j<p)
{
a[i++]=b[j++];
}
}
#if0
printf("===========%d============
",count);
count++;
//Displaythesorteddata.
for(i=0;i<p;i++)
{
printf("%d",b[i]);
}
printf("
");
for(i=0;i<q;i++)
{
printf("%d",c[i]);
}
printf("
");
for(i=0;i<p+q;i++)
{
printf("%d",a[i]);
}
printf("
");
#endif
}
voidMergesort(inta[],intn)
{
intb[n],c[n];
inti,j,k;
//Initialize...
j=0;
k=0;
if(n>1)
{
for(i=0;i<=n/2-1;i++)//前半部分复制到b数组中
{
b[j++]=a[i];
}
for(i=n/2;i<=n-1;i++)//后半部分复制到c数组中
{
c[k++]=a[i];
}
Mergesort(b,n/2);
Mergesort(c,n-n/2);
Merge(b,n/2,c,n-n/2,a);
}
}
intmain()
{
intn,a[100],i;
printf(":");
scanf("%d",&n);
printf(":
");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
n_data=n;
//sort...
Mergesort(a,n);
//Displaythesorteddata.
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}
printf("
");
}

问题应该出现在这里 函数Merge内 while (i<p && j<q) 这处条件。

（写代码最好要参照一些规范，你的代码逻辑方面不好读，我这边帮你改了一部分，主要是{}的问题。）

还有，这个代码功能比较隐晦，不太好理解。如果是归并排序的话，可以参考网络上的C代码。如下：（感觉要比你的代码容易理解）

#include<stdlib.h>
#include<stdio.h>

voidMerge(intsourceArr[],inttempArr[],intstartIndex,intmidIndex,intendIndex)
{
inti=startIndex,j=midIndex+1,k=startIndex;
while(i!=midIndex+1&&j!=endIndex+1)
{
if(sourceArr[i]>sourceArr[j])
tempArr[k++]=sourceArr[j++];
else
tempArr[k++]=sourceArr[i++];
}
while(i!=midIndex+1)
tempArr[k++]=sourceArr[i++];
while(j!=endIndex+1)
tempArr[k++]=sourceArr[j++];
for(i=startIndex;i<=endIndex;i++)
sourceArr[i]=tempArr[i];
}

//内部使用递归
voidMergeSort(intsourceArr[],inttempArr[],intstartIndex,intendIndex)
{
intmidIndex;
if(startIndex<endIndex)
{
midIndex=(startIndex+endIndex)/2;
MergeSort(sourceArr,tempArr,startIndex,midIndex);
MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
}
}

intmain(intargc,char*argv[])
{
inta[8]={50,10,20,30,70,40,80,60};
inti,b[8];
MergeSort(a,b,0,7);
for(i=0;i<8;i++)
printf("%d",a[i]);
printf("
");
return0;
}