归并排序 C++实现

// 归并排序.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;
typedef int DataType;

//合并data1[begin...mid]和data1[mid+1.end]到data2[begin,end]中,然后复制到data1[begin,end]中
void merge(DataType *data1,DataType *data2,int begin,int mid,int end)
{
int i,j,k;
for(i = begin,j=mid+1,k = begin;i<=mid&&j<=end;k++)
{
if(data1[i]<=data1[j])
data2[k] = data1[i++];
else
data2[k] = data1[j++];
}
if(i<=mid)
while(i<=mid)
data2[k++] = data1[i++];
else
while(j<=end)
data2[k++] = data1[j++];
for(i=begin;i<=end;i++)
data1[i] = data2[i];
}

//归并排序
void Msort(DataType *data1,DataType *data2,int begin,int end)
{
if(begin==end)
data1[begin] = data1[begin];
else
{
int mid = (begin+end)/2;
Msort(data1,data2,begin,mid);
Msort(data1,data2,mid+1,end);
merge(data1,data2,begin,mid,end);
}
}

int _tmain(int argc, _TCHAR* argv[])
{

//data1存储原数据和排序后的数据，data2为辅助数据
DataType data1[N],data2[N];
int cases;
cout<<"请输入案例个数：";
cin>>cases;
while(cases--)
{
int n;
cout<<"请输入元素个数：";
cin>>n;
int i;
cout<<"请输入待排序元素："<<endl;
for(i=1;i<=n;i++)
cin>>data1[i];
cout<<"归并排序前："<<endl;
for(i=1;i<=n;i++)
cout<<data1[i]<<" ";
cout<<endl;
Msort(data1,data2,1,n);
cout<<"归并排序后："<<endl;
for(i=1;i<=n;i++)
cout<<data1[i]<<" ";
cout<<endl;
}
system("pause");
return 0;
}

--------------------------------------------------测试程序-----------------------------------------------------请输入案例个数：2
请输入元素个数：9
请输入待排序元素：
87 65 2 77 88 54 2 7 8
归并排序前：
87 65 2 77 88 54 2 7 8
归并排序后：
2 2 7 8 54 65 77 87 88
请输入元素个数：10
请输入待排序元素：
10 9 8 7 6 5 4 3 2 1
归并排序前：
10 9 8 7 6 5 4 3 2 1
归并排序后：
1 2 3 4 5 6 7 8 9 10
请按任意键继续. . .