#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#define MAX_SIZE 10
void Double_Merge(ElemType r1[],int left, int mid, int right, ElemType r2[])
/已知r1[left,mid]和r1[mid+1,right]已分别有序排列,
将它们合并成一个有序序列放在r2[left,right]/
{
int i=0, j=0, k=0;
i=left;
j=mid+1;
k=left; // r2的索引
while ((i<=mid) && (j<=right))
{
if (r1[i] <= r1[j])
{
r2[k] = r1[i];
i++;
}
else // r1[j] < r1[i]
{
r2[k] = r1[j];
j++;
}
k++;
}
while (i<=mid) // j > right右半已读完
{
r2[k] = r1[i]; // 读取左边剩下的
k++;
i++;
}
while (j<=right) // i>mid左半已读完
{
r2[k] = r1[j];
k++;
j++;
}
}
void Double_Sort(ElemType r1[], int left, int right, ElemType r3[])
{
ElemType *ptr_r2; // 辅助空间
ptr_r2=(ElemType *)malloc((right-left+1) * sizeof(ElemType));
int mid=0;
if(ptr_r2 == NULL)
{
printf("\n Sorry,Can not Allocate Memory For r2!");
exit(-100);
}
if(left==right) // 只有一个元素
{
r3[left]=r1[left];
}
else
{
mid=(left+right)/2;
Double_Sort(r1,left,mid,ptr_r2); // 排序左半序列 放到r2
Double_Sort(r1,mid+1,right,ptr_r2); // 排序右半序列 放到r2
Double_Merge(ptr_r2,left,mid,right,r3); // 左右合并到r3
}
free(ptr_r2);
}
int main(void)
{
int i = 0;
ElemType source[MAX_SIZE], dest[MAX_SIZE];
for (i=0;i<MAX_SIZE;i++)
{
source[i] = 20 * (MAX_SIZE - i);
dest[i] = 0;
}
printf("\n 排序前:\n");
for (i=0; i<MAX_SIZE;i++)
{
printf("%d\t", source[i]);
if((i+1)%10 == 0)
{
printf("\n");
}
}
Double_Sort(source, 0, MAX_SIZE-1, dest);
printf("\n 排序后:\n");
for (i=0; i<MAX_SIZE;i++)
{
printf("%d\t", dest[i]);
if((i+1)%10 == 0)
{
printf("\n");
}
}
return 0;
}