#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 = jq <= rq++ ) d[ k++ ] = c[ q ]
else
for( int q = iq <= mq++ ) d[ k++ ] = c[ q ]
}void Copy( int c[], int d[], int n1, int n2 )
{
for( int i = n1i <= n2i++ )
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 = 0i <10i++ ) a[ i ] = rand() % 100//随机生成
for( i = 0i <10i++ ) //输出随机生成的数据
printf( "%d\t", a[ i ] )
printf( "\n" )
MergeSort( a, 0, 9 )
for( i = 0i <10i++ ) //输出排序后的结果
printf( "%d\t", a[ i ] )
printf( "\n" )
return 0
} //在vc++6.0上调试运行成功。若有不明白的地方,call me!!!
void MergeSort(int x[],int n) { //非递归归并排序//元素数组为x,其长度为n
int i,j,k1,k2,l
int *a
for(i=1i<=n-1i=i*2)//i为插入排序的子段长度
{
for(j=1j<=n-1j=j+2*i)//j为进行插入排序的子段起始位置
{
a=(int *)malloc(2*i*sizeof(int))
l=0k1=jk2=j+i
while((l<2*i)&&(k2<=n-1)&&(k2<j+2*i)&&(k1<j+i))
{//子段中,比较,移至辅助内存
if(x[k1]<x[k2])
{
a[l++]=x[k1]k1++
}
else
{
a[l++]=x[k2]k2++
}
}
if((k2>n-1)||(k2>=j+2*i))
{//子段的后一段超出数组范围
for(k1<j+ik1++)
a[l++]=x[k1]
}
else//就只有第一段就超数组了
{
if(k1>=j+i)
{
for((k2<j+2*i)&&(k2<=n-1)k2++)
a[l++]=x[k2]
}
}
for(k1=0k1<lk1++)//最后移位
{
x[j+k1]=a[k1]
}free(a)
}
}
}
非递归的归并排序,我以前写的。
中间malloc与free的话,是为了方便管理不定大小的空间,这里需要malloc.h的头文件
//MergeSort.cpp#include <iostream.h>
#include <conio.h>
#define MAXSIZE 20
#define LENGTH 7
typedef int RedType
typedef struct //SqList structure
{ RedType r[MAXSIZE+1] //Records Type
int length
}SqList
typedef SqList RcdType
void Merge(RcdType SR,RcdType &TR,int i,int m,int n) //Merge() function
{ int j,k
for(j=m+1,k=ii<=m&&j<=n++k)
{ if(SR.r[i]<=SR.r[j])
TR.r[k]=SR.r[i++]
else
TR.r[k]=SR.r[j++]
}
while(i<=m)
TR.r[k++]=SR.r[i++]
while(j<=n)
TR.r[k++]=SR.r[j++]
}//end of Merge() function
void MSort(RcdType SR,RcdType &TR1,int s, int t) //MSort() function
{ int m
RcdType TR2//[LENGTH]
if(s==t)
TR1.r[s]=SR.r[t]
else
{ m=(s+t)/2
MSort(SR,TR2,s,m)
MSort(SR,TR2,m+1,t)
Merge(TR2,TR1,s,m,t)
}//end of else
}//end of MSort() function
void MergeSort(SqList &L) //MergeSort() function
{
MSort(L,L,1,L.length)
}//end of MergeSort() function
void main() //main function
{ int i
SqList L//={{0,49,38,65,97,76,13,27,},LENGTH}
cout<<"MergeSort.cpp"<<endl<<"============="<<endl<<endl
cout<<"Please input the length of SqList L: <eg. 7>"
cin>>L.length
cout<<"Please input the disordered array L.r: <eg. {49,38,65,97,76,13,27,...}>"<<endl
for(i=1i<=L.lengthi++)
cin>>L.r[i]
MergeSort(L)
cout<<endl<<"The sorted array L.r: "
for(i=1i<=L.lengthi++)
cout<<L.r[i]<<" "
cout<<endl
cout<<"...OK!..."<<endl
getch()
}//end of main() function我以前的,可以调试的
应该符合你要求,只是很少部分你自己改一下,比如数的个数
输入改为 rand()随即输入,刚才粘贴错了