归并排序
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int KeyType;
typedef char ElemType[10];
typedef struct
{
KeyType key;
ElemType data;
} LineList;
void Merge(LineList R[],int low,int mid,int high)
{
LineList *R1;
int i=low,j=mid+1,k=0;
R1=(LineList *)malloc((high-low+1)*sizeof(LineList));
while (i<=mid && j<=high)
if (R[i].key<=R[j].key)
{ R1[k]=R[i];
i++;k++;
}
else
{ R1[k]=R[j];
j++;k++;
}
while (i<=mid)
{
R1[k]=R[i];
i++;k++;
}
while (j<=high)
{ R1[k]=R[j];
j++;k++;
}
for (k=0,i=low;i<=high;k++,i++)
R[i]=R1[k];
}
void MergePass(LineList R[],int length,int n)
{
int i;
for (i=0;i+2*length-1<n;i=i+2*length)
Merge(R,i,i+length-1,i+2*length-1);
if (i+length-1<n)
Merge(R,i,i+length-1,n-1);
}
void MergeSort(LineList R[],int n)
{
int length;
for (length=1;length<n;length=2*length)
MergePass(R,length,n);
}
void main()
{
LineList R[MaxSize];
KeyType a[]={75,87,68,92,88,61,77,96,80,72};
int n=10,i;
for (i=0;i<n;i++)
R[i].key=a[i];
printf("排序前:");
for (i=0;i<n;i++)
printf("%3d",R[i].key);
printf("\n");
MergeSort(R,n);
printf("排序后:");
for (i=0;i<n;i++)
printf("%3d",R[i].key);
printf("\n");
}