首先，我对唐纳德·希尔这个人还是很欣赏的，哈哈。。理解了他的希尔排序算法以后，我大为震惊。一方面由于他既然可以想到这么令人震撼的方法，另一方面是我曾在大一的时候想过是否可以这样分类以排序，结果我没坚持下来实现，所以看到希尔居然实现的时候，一方面震惊于他的思想，另一方面惋惜当时没有真的写出来。
言归正传，希尔排序究竟是一个什么鬼，，我不知道怎么描述，，，总之，简单来说就是先把一个待排序的线性表按照len/2划分【希尔最初这样划分，但是究竟如何划分效率高没有严格的数学证明】，gap=len/2,这样从gap开始，所有距离为gap的对象为一个子序列，将这些子序列直接插入排序。然后将gap=gap/2继续缩小空间进行子序列直接插入排序，这样直到gap为1的时候在排列一次时就全部完成了。
这个算法的绝妙之处在于每次缩小隔间之后的分组的元素中都是来自上一次分组中不同的元素，这样就相当于把上一次未排列的数排列了一下。由于前面已经做好小组的排序工作，后面的大组排序将变得简单。这个过程意会以后有种和线性代数中行列式的计算定义一样。。。好神奇的感觉。。。下面代码有个bug,只能排序偶数个数，电影快赶不上了，，if/else有时间加吧QAQ......
include<iostream>
include<vector>
using namespace std;
class ShellSort{
private:
int len;
vector<int> list;
public:
ShellSort(vector<int> _list, int _len);
void shell_sort();
void out();
};
ShellSort::ShellSort(vector<int> _list, int _len){
for(int i=0; i<len; i++) list.push_back(_list[i]);
this->len = _len;
}
void ShellSort::shell_sort(){
int grap = len/2;
int digit;
while(grap){
for(int i = grap; i<len; i++){
digit = list[i];
int j=i;
while(j>=grap && digit<list[j-grap]){
list[j] = list[j-grap];
j -= grap;
}
list[j] = digit;
}//end for i
grap = grap/2;
}
}
void ShellSort::out(){
for(int i=0; i<len; i++) cout<<list[i];
}
int main(){
int array[8] = {8,7,6,5,4,3,2,1};
vector<int> list;
for(int i=0; i<8; i++) list.push_back(array[i]);
ShellSort mazhe(list,8);
mazhe.shell_sort();
mazhe.out();
return 0;
}
