目录
个人评价
一个很天才的想法，对插入排序进行一点更改，代码很简略但是非常的快
和堆排序可以坐在一张桌上
原理
一般的插入排序都是以1为单位进行比较
越有序，插入排序越快
希尔排序就是一个使数组不断趋近有序的排序，和插入排序有异曲同工之妙
希尔排序是一种间隔的排序
希尔排序分为两步
1.预排序
2.插入排序
例如
以3为间隔
可以分成三组
对每组都单独进行插入排序，这样就可以以很小的代价使数组趋向有序，插入排序也就越快
我们不断缩小间隔，可以使数组不断趋近有序，插排也就越快
间隔大小
插排的间隔并没有明确答案，但是一般间隔
gap=sum/3+1
gap=gap/3+1
这样做可以保证最后gap为1，而且间隔大小是随数组大小变化而变化
但是学校里上课一般gap=sum/2,gap=gap/2
时间复杂度
非常复杂，对于绝大部分人来说完全无法计算
例如
一开始间隔100，分为3组
我们假设一开始就是最差情况，那么需要排序100*(1+2)=300
但是从第二组开始
直接乱掉了
因为第二组开始就没法保证是最差情况了，因为第一组时就已经排过序了，打乱间隔也没法确保就是最差情况
对于我这计算水平来说肯定是算不出来的
但是根据大量数据可以得出
希尔排序的时间复杂度大概为
O(N^1.3)
比起冒泡，插排等等排序要快上许多，可以和复杂度为O(NlogN)的堆排序进行比较
代码
void shellsort(int* arr, int sum) {
int gap=sum, begin, end, tmp,i;
while (gap > 1) {
gap = gap / 3 + 1;
for (begin = 0; begin < gap; begin++) {
for (i = begin; i < sum - gap; i += gap) {
end = i;
tmp = arr[i + gap];
while (end >= 0) {
if (arr[end] > tmp) {
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = tmp;
}
}
}
}