归并排序

  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. }