希尔排序，也就是对于一列数据，对间隔为k的数据进行排序，也就是对于 1、1+k、1+2×k....；2、2+k、2+2×k、....；..... 分别进行排序，这样 间隔为k 的数据就是有序的了，然后逐渐减小k的值，知道k为1的时候，也就是对整个数列进行完整的排序了。
希尔排序关键的地方是 k值怎么确定，k为多少的时候效率最高，一般来说 是2n-1,2n-1-1,.......1 这样的k比较好。
关键代码如下：
template<typename Iterator,typename
Obj>
void __shellSort(Iterator first,Iterator
last ,int n,Obj)
{
for(Iterator
iter=first+n;iter!=last;++iter)
{
Obj
obj=*iter;
Iterator
_iter;
for(_iter=iter;_iter>=first+n;_iter-=n)
{
if(*(_iter-n)>obj)
*(_iter)=*(_iter-n);
else
break;
}
*_iter=obj;
}
}
基本实现代码如下：（Shell_Sort.h)
#ifndef ___SHELL_SORT_H
#define ___SHELL_SORT_H
template<typename Iterator,typename
Obj>
void __shellSort(Iterator first,Iterator
last ,int n,Obj)
{
for(Iterator
iter=first+n;iter!=last;++iter)
{
Obj
obj=*iter;
Iterator
_iter;
for(_iter=iter;_iter>=first+n;_iter-=n)
{
if(*(_iter-n)>obj)
*(_iter)=*(_iter-n);
else
break;
}
*_iter=obj;
}
}
template<typename Iterator>
void _shellSort(Iterator first,Iterator
last,int n)
{
return
__shellSort(first,last,n,*first);
}
template<typename Iterator>
void shellSort(Iterator first,Iterator
last,int k)
{
for(int
i=k;i!=0;--i)
{
int
interval=1;
for(int
j=1;j<=i;++j)
interval*=2;
interval-=1;
_shellSort(first,last,interval);
}
}
template<typename Iterator>
void shellSort(Iterator first,Iterator
last)
{
int
interval=last-first;
int
count=0;
for(int
sum=1;sum<=interval;sum=2*sum+1)++count;
return
shellSort(first,last,count);
}
#endif
测试代码如下：test.cpp
#include "Shell_Sort.h"
#include<time.h>
#include <iostream>
using namespace std;
int main()
{
cout<<"The
raw datas are:"<<endl;
srand((int)time(0));
int
iArray[100];
for(int
i=0;i!=100;++i)
{
iArray[i]=rand()%200;
cout<<iArray[i]<<"/t";
}
cout<<endl;
cout<<"After
sort,these datas are:"<<endl;
shellSort(iArray,iArray+100);
for(int
i=0;i!=100;++i)
cout<<iArray[i]<<"/t";
cout<<endl;
system("pause");
return
0;
}