• 归并排序

    归并排序

    1. #include <stdio.h>
    2. #include <malloc.h>
    3. #define MaxSize 100
    5. typedef int KeyType;        /*关键字类型*/
    7. typedef char ElemType[10];    /*其他数据项类型*/
    9. typedef struct 
    10. {    
    11.     KeyType key;               /*关键字域*/
    12.     ElemType data;             /*其他数据域*/
    13. } LineList;                    /*线性表元素类型*/
    15. void Merge(LineList R[],int low,int mid,int high) 
    16. {
    17.     LineList *R1;
    18.     int i=low,j=mid+1,k=0; /*k是R1的下标,i、j分别为第1、2段的下标*/
    19.     R1=(LineList *)malloc((high-low+1)*sizeof(LineList));  /*动态分配空间*/
    20.     while (i<=mid && j<=high)    /*在第1段和第2段均未扫描完时循环*/
    21.         if (R[i].key<=R[j].key)  /*将第1段中的记录放入R1中*/
    22.         {    R1[k]=R[i];
    23.             i++;k++; 
    24.         }
    25.         else                           /*将第2段中的记录放入R1中*/
    26.         {    R1[k]=R[j];
    27.             j++;k++; 
    28.         }
    29.         while (i<=mid)               /*将第1段余下部分复制到R1*/
    30.         {  
    31.             R1[k]=R[i];
    32.             i++;k++; 
    33.         }
    34.         while (j<=high)           /*将第2段余下部分复制到R1*/
    35.         {    R1[k]=R[j];
    36.             j++;k++;  
    37.         }
    38.         for (k=0,i=low;i<=high;k++,i++) /*将R1复制回R中*/
    39.             R[i]=R1[k];
    40. } 
    42. void MergePass(LineList R[],int length,int n)
    43. {
    44.     int i;
    45.     for (i=0;i+2*length-1<n;i=i+2*length)     /*归并length长的两相邻子表*/
    46.         Merge(R,i,i+length-1,i+2*length-1);
    47.     if (i+length-1<n)                    /*余下两个子表,后者长度小于length*/
    48.         Merge(R,i,i+length-1,n-1);     /*归并这两个子表*/
    49. }
    51. void MergeSort(LineList R[],int n)    /*二路归并算法*/
    52. {
    53.     int length;
    54.     for (length=1;length<n;length=2*length)
    55.         MergePass(R,length,n);
    56. }
    58. void main()
    59. {
    60.     LineList R[MaxSize];
    61.     KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    62.     int n=10,i;
    63.     for (i=0;i<n;i++)
    64.         R[i].key=a[i];
    65.     printf("排序前:");
    66.     for (i=0;i<n;i++)
    67.         printf("%3d",R[i].key);
    68.     printf("\n");
    69.     MergeSort(R,n);
    70.     printf("排序后:");
    71.     for (i=0;i<n;i++)
    72.         printf("%3d",R[i].key);
    73.     printf("\n");
    74. }