希尔排序

  1. #include <stdio.h>
  2. #define MaxSize 100
  4. typedef int KeyType;        /*关键字类型*/
  6. typedef char ElemType[10];    /*其他数据项类型*/
  8. typedef struct 
  9. {    
  10.     KeyType key;               /*关键字域*/
  11.     ElemType data;             /*其他数据域*/
  12. } LineList;                    /*线性表元素类型*/
  14. void ShellSort(LineList R[],int n)
  15. {
  16.     int i,j,gap;
  17.     LineList tmp;
  18.     gap=n/2;                    /*增量置初值*/
  19.     while (gap>0)
  20.     {    
  21.         for (i=gap;i<n;i++)      /*对所有相隔gap位置的所有元素组进行排序*/
  22.         {
  23.             tmp=R[i];
  24.             j=i-gap;
  25.             while (j>=0 && tmp.key<R[j].key)/*对相隔gap位置的元素组进行排序*/
  26.             {
  27.                 R[j+gap]=R[j];
  28.                 j=j-gap;                    /*移到本组中的前一个元素*/
  29.             }
  30.             R[j+gap]=tmp;
  31.             j=j-gap;
  32.         }
  33.         gap=gap/2;    /*减小增量*/
  34.     }
  35. }
  37. void main()
  38. {
  39.     LineList R[MaxSize];
  40.     KeyType a[]={75,87,68,92,88,61,77,96,80,72};
  41.     int n=10,i;
  42.     for (i=0;i<n;i++)
  43.         R[i].key=a[i];
  44.     printf("排序前:");
  45.     for (i=0;i<n;i++)
  46.         printf("%3d",R[i].key);
  47.     printf("\n");
  48.     ShellSort(R,n);
  49.     printf("排序后:");
  50.     for (i=0;i<n;i++)
  51.         printf("%3d",R[i].key);
  52.     printf("\n");
  53. }