//希尔排序
//思想来源，1.在n不大 2.元素基本有序的时候 直接插效果非常好
//所以我们分组，然后进行直接插，到最后就是一个基本有序的大序列，最后来一次直接插

include[HTML_REMOVED]

using namespace std;

void shellsort(int data[],int n){
//这里理解为直接插入套个壳子
//但是也有不同，要注意越下界问题
for(int b=n/2;b>=1;b/=2){//这是希尔给的增量序列
for(int i=b+1;i<=n;i++){//隔b个算一组，所以前b个是每个组的头头
//直接插入是从每个组的第二个元素开始排序，所以从b+1开始
//算法微观理解其实是每个组轮流处理
if(data[i][HTML_REMOVED]=1&&data[j]>data[0]){//这里注意下界问题
data[j+b]=data[j];
j-=b;
}
data[j+b]=data[0];
}
}
}
}

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
cout<<endl;
shellsort(data,10);
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
}

//分析
//希尔排序时间复杂度和d有关，不好分析，一般认为n的1.3次方
//这里西大书只给了这个，王道上面说最坏情况还是n²
//空间O(1)
//适合中等元素n吧
//不稳定，相同的关键字可能分到不同的组，相对次序改变

//这里使用了随机存储，所以链式不能用