#include

#include

#include

#include

#define random(i) (rand()%i)

#define N 12

#define INFINITY 99999999

//要排序的數存放在a數組匯總，p,q,r是數組下標

void Merge(int *a,int p,int q,int r)

{

int n1=q-p+1;

int n2=r-q;

int *L=(int *)malloc(sizeof(int)*n1);

int *R=(int *)malloc(sizeof(int)*n2);

int i,j,k;

int m=0;

if(L==NULL)

{

printf("申請空間失敗\\n");

}

if(R==NULL)

{

printf("申請空間失敗\\n");

}

for(i=0;i

{

L[i++]=a[p+i];

i--;

}

for(j=0;j

{

R[j++]=a[q+j+1];

j--;

}

L[n1]=INFINITY; //設置哨兵

R[n2]=INFINITY;

i=0;

j=0;

for(k=p;k<=r;k++)

{

if(L[i]<=R[j])

{

a[k]=L[i];

i++;

}

else

{

a[k]=R[j];

j++;

}

}

}

void merge_sort(int *A,int p,int r)

{

int q;

if(p

{

q=(p+r)/2;

merge_sort(A,p,q);

merge_sort(A,q+1,r);

Merge(A,p,q,r);

}

}

void main()

{

int rand_no=0;

int i=0;

int j=0;

int a[N]; //n表示數組長度

srand((int)time(0)); //設置隨機數種子

printf("==================排序前==========================");

printf("\\n");

for(rand_no=0;rand_no

{

a[rand_no]=random(100);

printf("%5d",a[rand_no]);

}

printf("\\n");

merge_sort(a,0,N);

printf("==================排序后==========================");

printf("\\n");

for(i=1;i<=N;i++)

printf("%5d",a[i]);

printf("\\n");

}