/*算法思想簡單描述：
 算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中
 記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量
 對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數(shù)被分成
 一組，排序完成。 
 函數(shù)初次取序列的一半為增量，以后每次減半，直到增量為1.*/
#include<iostream.h>//希爾排序
#define MAX 4
void shell_sort(int a[],int n);
int main()
{ 
   int *p, i,n,a[MAX];
   n=MAX;
   p=a;

   cout<<"Input "<<n<<" number for sorting :"<<endl;
   for(i=0;i<MAX;i++)
   {
	 cin>>a[i];
   }
   cout<<endl;
   shell_sort(p,MAX);

   cout<<"After shell_sort:"<<endl;
   for(i=0;i<MAX;i++)
   {
     cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}

void shell_sort(int a[],int n)//希爾排序
{
   int h,j,k,t;

   for(h=n/2;h>0;h=h/2) //控制增量
   {
       for(j=h;j<n;j++) //這個實際上就是上面的直接插入排序
	   {
          t=a[j];
          for(k=j-h;(k>=0&&t<a[k]);k-=h)
		  {
             a[k+h]=a[k];
		  }
          a[k+h]=t;
	   }
   }
}