归并排序MergeSort: 设将两个相邻的有序子序列r[s]~r[m]和r[m+1] ~r[t]合并为一个有序序列r1[s] ~r1[t],函数Merge实现合并操作。归并排序算法用C++语言描述如下：
#include<iostream> using namespace std; 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++]; //取r[i]和r[j]中较小者放入r1[k] else r1[k++]=r[j++]; } while(i<m) r1[k++]=r[i++]; //若第一个子序列没处理完，则进行收尾 while(j<=t) r1[k++]=r[j++]; //若第一个子序列没处理完，则进行收尾 } void MergeSort(int r[],int s,int t) //对序列r[s]~r[t]进行归并排序 { int m,r1[1000]; //数组r1是临时数组,假设最多1000个 if(s==t) return ; //递归的边界条件，只有一个记录,已经有序 else { m=(s+t)/2; //划分 MergeSort(r,s,m); //求解子问题1,归并排序前半个子序列 MergeSort(r,m+1,t); //求解子问题1,归并排序后半个子序列 Merge(r,r1,s,m,t); //合并两个有序子序列，结果存在数组r1中 for(int i=s;i<=t;i++) //将有序数组传回数组r中 r[i]=r1[i]; } } int main() { int array[1000]; int n; cin>>n; for(int k=0;k<n;k++) cin>>array[k]; MergeSort(array,0,n-1); for(int k=0;k<n-1;k++) cout<<array[k]<<" "; cout<<array[n-1]<<endl; return 0; }