shells.cpp

非常全的排序算法c实现

/*算法思想简单描述：
 算法先将要排序的一组数按某个增量d分成若干组，每组中
 记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
 对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
 一组，排序完成。 
 函数初次取序列的一半为增量，以后每次减半，直到增量为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;
	   }
   }
}