/* ======================================== */
/*    程序實例: 10_5b.c                     */
/*    希爾排序法(自定增量)                  */
/* ======================================== */
#include <stdlib.h>
#define MAX  20                   /* 最大字符串長度       */

/* ---------------------------------------- */
/*  希爾排序法                              */
/* ---------------------------------------- */
void shell(char *string,int count)
{
   int offset_a[6] = { 11, 7, 5, 3,   /* 設定處理增量   */
                        2, 1 };
   int pos;                       /* 處理位置           */
   int offset;                    /* 位移量             */
   int i,j;
   char temp;

   for ( i = 0; i < 6 ; i++ )     /* 處理六次增量       */
   {
      offset = offset_a[i];       /* 建立位移量         */
      for ( j = offset; j < count; j++ )  /* 交換循環   */
      {
         temp = string[j];        /* 保留其值           */
         pos = j - offset;        /* 計算處理位置       */
         while ( temp < string[pos] &&    /* 比較       */
                 pos >= 0 && j <= count)
         {
            /* 交換其值 */
            string[pos+offset] = string[pos];
            pos = pos - offset;   /* 下一個處理位置     */
         }
         string[pos+offset] = temp;   /* 與最后元素交換 */
      }
      printf("輸出結果: [%s]\n",string); /*輸出處理字符串 */
   }
}

/* ---------------------------------------- */
/*  主程序: 輸入字符串后將字符串排序           */
/* ---------------------------------------- */
void main()
{
   char string[MAX];              /* 字符串數組           */
   int count;                     /* 字符串長度           */

   printf("輸入要排序的字符串 ==> ");
   gets(string);                  /* 讀取字符串           */
   count = strlen(string);        /* 計算字符串長度       */
   shell(string,count);           /* 希爾排序法         */
   /* 輸出排序后字符串 */
   printf("\n輸出排序結果: [%s]\n",string);
}