|
合并排序算法
问题描述：用分治策略实现对n个元素进行排序。
算法思想：将待排序的元素划分为两个等长相等的子序列，分别对这两个子序列进行排序，最终将这两个有序的子序列合并成所要求的有序序列。
图
归并排序算法：
void MergeSort(int left,int right,int a[])
{
Back;
int mid=(i+j)/n;
al=MergeSort(left,mid,a);
ar=MergeSort(mid+1,right,a);
Merge();
return;
}
?Back为递归边界，用来返回，al为MergeSort函数返回的左子问题，ar为MergeSort函数返回的右子问题，最后用Merge合并函数来合并两个子问题（这里的返回和合并并未用对应函数单独来描述）
递归边界代码：
if(i==j)
{
c[0]=a[i];
return c;
}
if(i==j-1)
{
if(a[i]>a[j])
{
c[0]=a[j];
c[1]=a[i];
return c;
}
if(a[i]<a[j])
{
c[0]=a[i];
c[1]=a[j];
return c;
}
}
递归函数代码（划分子问题）：
mid=(i+j)/2;
int *al=sort(i,mid,a);
int *ar=sort(mid+1,j,a);
合并算法：
while(m<=mid&&n<=j-mid-1)
{
if(al[m]>ar[n])
c[k++]=ar[n++];
if(al[m]<ar[n])
c[k++]=al[m++];
}
if(m==mid+1)
{
while(n<=j-mid)
c[k++]=ar[n++];
}
if(n==j-mid)
{
while(m<=mid)
c[k++]=al[m++];
}
return c;
注意：
1.因为C++中函数无法返回数组，所以必须利用指针（上链接）。
2.在函数中利用三个数组，数组c[]用来合并左右子问题最后返回一个已经排序的数组。al[]数组用来记录左子问题返回的已排好序的数组,ar[]数组用来记录右子问题返回的已排好序的数组。
3.在合并算法中要注意n<=j-mid-1，j-mid-1是右边子问题的右边界，不能单纯的写为j。
最终代码如下：
#include<stdio.h>
#include<windows.h>
int *sort(int i,int j,int a[])
{
int mid,m,n,k,*c=new int[100];
m=n=k=0;
if(i==j)
{
c[0]=a[i];
return c;
}
if(i==j-1)
{
if(a[i]>a[j])
{
c[0]=a[j];
c[1]=a[i];
return c;
}
if(a[i]<a[j])
{
c[0]=a[i];
c[1]=a[j];
return c;
}
}
mid=(i+j)/2;
int *al=sort(i,mid,a);
int *ar=sort(mid+1,j,a);
while(m<=mid&&n<=j-mid-1)
{
if(al[m]>ar[n])
c[k++]=ar[n++];
if(al[m]<ar[n])
c[k++]=al[m++];
}
if(m==mid+1)
{
while(n<=j-mid)
c[k++]=ar[n++];
}
if(n==j-mid)
{
while(m<=mid)
c[k++]=al[m++];
}
return c;
}
void main(){
int n,k,a[100];
printf("请输入问题规模:");
scanf("%d",&n);
printf("输入问题具体数字:\n");
for(k=0;k<=n-1;k++)
scanf("%d",&a[k]);
int *b=sort(0,n-1,a);
for(k=0;k<=n-1;k++)
printf("%d ",b[k]);
system("pause");
}
|