#include<stdio.h>
// 壹個遞歸函數
void mergesort(int *num,int start,int end);
// 這個函數用來將兩個排好序的數組進行合並
void merge(int *num,int start,int middle,int end);
int main()
{
// 測試數組
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 進行合並排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之後
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}
//這個函數用來將問題細分
void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 歸並的基本思想
// 排左邊
mergesort(num,start,middle);
// 排右邊
mergesort(num,middle+1,end);
// 合並
merge(num,start,middle,end);
}
}
//這個函數用於將兩個已排好序的子序列合並
void merge(int *num,int start,int middle,int end)
{
int n1=middle-start+1;
int n2=end-middle;
// 動態分配內存，聲明兩個數組容納左右兩邊的數組
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;
//將新建的兩個數組賦值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 進行合並
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}