希尔排序在介绍希尔排序之前，请先了解直接插入排序
文章目录希尔排序1、直接插入排序1、单次排序2、直接插入排序2、希尔排序3、测试希尔排序和直接插入排序性能1、直接插入排序1、单次排序
x插入一个有序区间
这里end是指向数组最后一个元素
2 .直接插入排序是根据上面的单列排序启发的
end是数组的最后一个元素，end之后的所有元素都要排序
一个重要的判断点是end和x比较大小
这里end x
需要进一步改善
你会发现有两个环路。 反向遍历一个循环中的end后，如果将第一个end结束的数组添加到x中，则会生成有序数组，最后返回到这个新数组中最后一个元素的位置
注意公共部分
end----； x=a[end 1]；外面是一个for循环，从第二个到最后一个元素
for(I=0； i n - 1； I ) { } 代码：
//插入排序voidinsetsort(int*a，int n ) intend=0； int i=0； for(I=0； i n - 1； I ) {end=i； int x=a[end 1]； while(end=0) ) if ) a[end]x ) {a[end 1]=a[end]； a[end]=x； }else{break； (end----)； }}} 时间复杂度O(N2)
测试：
int main () inta(4)={ 2，6，5，3 }； 插入(a，4； //外壳软件(a，4 )； int i=0； for(I=0； i 4； I ) {printf('%d '，a[i] )； }printf((n )； 返回0； }
二.希尔排序希尔排序法为缩小增量法
希尔排序法的基本思想首先选择整数，将排序对象文件中的所有记录分成gap组，将所有距离的记录分成同一个组，对各组中的记录进行排序。 然后重复上述分组和排序工作。 达到gap=1时，所有记录在统一组中进行排序。
希尔排序基于直接插入排序，先进行分组排序
以3个为一组进行排序
时间复杂度：
每次排可以看作长度为gap的数组直接插入排序
一共有gap组当然不是各组为gap/n个要素，但在数据相当多情况下，视为各排列中有gap/n个要素
所以(1+2……+n/gap)gap
当gap=1时，时间复杂度为O(n2)，相当于直接插入排序//希尔排序//希尔排序VoidShellsort(int*a，int n ) intend=0的int n int gap=n； //预排序while(gap1) )//最后一个数字必须是1gap=gap/2； for(I=0； i n - gap； I ) {end=i； //这里实际上是直接插入排序，但数组的各要素的间隔为gapint x=a[end gap]； while(end=0) ) if ) a[end]x ) {a[end gap]=a[end]； a[end]=x； end -=gap； }else{break； }}}}}测试用例仍然是上面的直接插入排序示例
结果还是成功了
三.希尔排序测试和直接插入排序的性能//性能测试void TestOP () (Srand ) Time ) )0)； 以1000个数字为例const int N=10000； int*a1=(int* ) malloc ) sizeof(int ) * N )； int*a2=(int* ) malloc ) sizeof(int ) ) n )； for(intI=0； i N； I () {a1[i]=rand )； a2[i]=a1[i]； //其中clock是到此为止运行的时间int begin1=clock (； 插入(a1，n )； int end1=clock (； int begin2=clock (； 壳核丸(A2，n )； int end2=clock (； //end-begin是排序所需的时间printf(%dn%dn )、end1 - begin1、end2 - begin2)； }
可以看出希尔排序比直接排序快得多，但希尔排序因为gap可以改变，目前没有一个统一的时间复杂度，先按照时间复杂度为O(n1.3)来吧