• 希尔排序

    希尔排序

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