二路歸並排序代碼

『壹』 求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;
}