l9_3.cpp

《数据结构（C++描述）》-李根强-源代码

//希尔排序
#include<iostream.h>
typedef int ElemType;
const int n=10;
ElemType a[n]={2,6,4,8,10,7,1,5,3,9};
void ShellSort(ElemType R[],int n)
{
  for  (int d=n/2; d>=1; d/=2) 
	  //d表示增量大小，增量每次整除2，第一次为n/2
  { for (int i=d; i<n; i++)
	{ //对每个元素直接插入到对应子序列的有序表中
      ElemType temp=R[i];   //将待插入对象暂存temp
      for(int j=i-d;j>=0;j-=d)
	  { //在组内向前顺序进行比较和移动
		  if(temp<R[j]) 
	    R[j+d]=R[j];
	    else break;//查找到合适位置就退出j循环
      }
	  R[j+d]=temp;
	}
}

}
void print(ElemType r[n])
{ int i;
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<endl;
}
void main()
{ cout<<endl<<"排序前的结果为:"<<endl;
 print(a);
ShellSort(a,n);
cout<<endl<<"排序后的结果为:"<<endl;
print(a);
}