分治法解决合并排序（c++和Java源代码）

public class Mergesort1 { public static void merge(int[]a,int low,int mid,int high){//对两组已经排序的数组进行合并
int[]b=new int[high-low+1]; //临时数组，存储个数为high - low + 1个数据
int s=low;
int t=mid+1;
int k=0;
while(s<=mid&&t<=high){ //直至前半部或后半部数据完全录入暂存
if(a[s]<=a[t]) //如果前半部的数据小于后半部的，前半部数据暂存
b[k++]=a[s++];
else //否则后半部数据暂存，并下标自加
b[k++]=a[t++];
}
while(s<=mid)
b[k++]=a[s++];
while(t<=high)
b[k++]=a[t++];
for(int i=0;i<b.length;i++){ //将暂存的数据重新填充至array[low]--array[high]中
a[low+i]=b[i];
}
}
public static void mergesort(int a[],int low,int high){//对数组进行递归排序
int mid;
if(low<high){
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}
public static void main(String[]args){
int[]a={4,34,2,56,5,9,6,45,8,3};
System.out.println("排序前数组为：");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" "); }
mergesort(a,0,a.length-1);
System.out.println("\n排序后数组为：");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");}
}}

#include <iostream>using namespace std;void Merge(int *array, int low, int middle, int high) //合并
{
int *A = new int[high - low + ]; //临时数组，存储个数为high - low + 1个数据
int i = low;
int j = middle + ;
int k = ;
while(i <= middle && j <= high) //直至前半部或后半部数据完全录入暂存
{
if(array[i] < array[j]) //如果前半部的数据小于后半部的，前半部数据暂存
A[k++] = array[i++];
else //否则后半部数据暂存，并下标自加
A[k++] = array[j++];
} while(i <= middle) //保证前半部数据录入暂存
A[k++] = array[i++];
while(j <= high) //保证后半部数据录入暂存
A[k++] = array[j++];
for(i = low; i <= high; i++) //将暂存的数据重新填充至array[low]--array[high]中
array[i] = A[i - low];
}void MergeSort(int *array, int low, int high)
{
int middle; //二分
if(low < high)
{
middle = (low + high) / ; //二分
MergeSort(array, low, middle); //前半部
MergeSort(array, middle + , high); //后半部
Merge(array, low, middle, high); //合并
}
}int main()
{
cout<<"输入需要排列数据的个数："; int n;
cin>>n; //录入需要排列的个数
int *array = new int[n];
cout<<endl<<"请输入数据："<<endl; for(int i = ; i < n; i++)
{
cin>>array[i]; //录入未排序的数据
} MergeSort(array, , n - ); //进行排序 cout<<"排列后数据："<<endl;
for(int j = ; j < n; j++) //输出排列结果
{
cout<<array[j]<<" ";
}
cout<<endl;
return ;
}