按我的想法,简单地说,合并排序的思路就是:
先递归,后排序。
#include<iostream>
using namespace std;
void merge_sort(int a[],int p,int r);
void merge(int a[],int p,int q,int r);
int b[20];
int main()
{
int a[11]={1,49,60,12,-12,101,121,62,60,8,-100};
int len=sizeof(a)/sizeof(a[0]);
merge_sort(a,0,len-1);
//输出结果
for(int i=0;i<len;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
void merge_sort(int a[],int p,int r)
{
int q=0;
if(p<r)
{
q=(p+r)/2;//拆分待排序元素
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);//将两个拆分后排好序的子序列合并起来
}
}
void merge(int a[],int p,int q,int r)
{
int b_index=0;
//局部排序
int i=q,j=r;
while(i>=p&&j>=q+1)
{
if(a[i]>=a[j])
{
b[b_index++]=a[i--];
}else{
b[b_index++]=a[j--];
}
}
//下面两个if用来处理剩余的元素
while(i>=p)
{
b[b_index++]=a[i--];
}
while(j>=q+1)
{
b[b_index++]=a[j--];
}
b_index--;
for(int i=p;i<=r;i++)
{
a[i]=b[b_index--];
}
}