#include
#include
#include
#include
using namespace std;
void merge(int a[], int p, int q, int r) {
int leftsize, rightsize, i, j, k;
leftsize = q - p + 1;
rightsize = r - q;
vector b(leftsize + 1, 0); // Define a vector with size of leftsize + 1 and initial value of 0
vector c(rightsize + 1, 0);// Define a vector with size of rightsize + 1 and initial value of 0
for(i=0;i<=leftsize;i++)
b[i]=a[i];
b[i+1]=0xffffff;
for(j=0;j<=rightsize;j++)
c[j]=a[(p+r)/2+j];
c[j+1]=0xffffff;
i=0;j=0;
for(k=0;k<=r;k++)
if(b[i]<=c[j])
a[k]=b[i++];
else
a[k]=c[j++];
}
void merge_sort(int a[],int p,int r)
{
int q;
if(p<r)
q=(p+r)/2;
merge_sort(a,p,q);
merge_sort(a,p+1,r);
merge(a,p,q,r);
}
void testMerge_Sort() {
int a[8]={7,6,2,7,7,8,7,1}, i;
printf("Before sorting, array a is\n");
for (i = 0; i < sizeof(a)/sizeof(int); ++i)
printf("%d",a[i]);
merge_sort(a, 0, sizeof(a)/sizeof(int)-1);
printf("\nAfter sorting, array a is\n");
for (i = 0; i < sizeof(a)/sizeof(int); ++i)
printf("%d ", a[i]);
printf("\n");
}
int main() {
testMerge_Sort();
return 0;
}
谢谢大家
