此算法比任何其他排序算法都要鬼畜！请做好心理准备
我们现在有一个序列，怎么对它排序？
这是一个非常经典的问题，这里我们使用一个不经典的鬼畜算法——希尔排序解决。
这里有一个序列，要对它升序排序（为便于取
gap
\text{gap}
gap，大小取
8
8
8）。
4
8
1
5
3
2
7
6
然后取
gap
=
n
2
=
4
\text{gap}=\frac n 2=4
gap=2n=4，将相距等于
gap
\text{gap}
gap 的两个元素分为一组，此处将不同组使用不同颜色标出
4
8
1
5
3
2
7
6
然后在每一组内进行排序（此时可自选一种其他排序，建议选取对较有序序列友好的算法。你要是直接启发式合并他不就变成归并了吗）
3
2
1
5
4
8
7
6
将
gap
\text{gap}
gap 减半，重新分组
3
2
1
5
4
8
7
6
继续操作，直至
gap
\text{gap}
gap 降为
1
1
1，即只剩下一组
1
2
3
5
4
6
7
8
1
2
3
5
4
6
7
8
1
2
3
4
5
6
7
8
此处使用插入排序作为辅助排序
void InsertionSort(int a[],int n,int x,int gap){
int tmp=a[i],j;
for (j=x;j>=gap&&a[j-gap]>tmp;j-=gap)
a[j]=a[j-gap];
a[j]=tmp;
}
void ShellSort(int a[],int n){
for (int gap=n/2;gap>=1;gap/=2)
for (int i=1;i<gap;i++)
InsertionSort(a,n,x,gap);
}