1、如何进行希尔排序

希尔排序是直接插入排序的优化，具体实现是先进行以gap间隔分别进行排序，将数组排成快要接近有序，最后一次gap为1的排序，实际上是直接插入排序，因为直接插入排序在接近有序时时间复杂度最小，所以以此进行优化，gap大于1的排序称为预排序。


2、程序

voidShellSort(int*a,size_tsize){assert(a);intgap=size;while(gap>1){gap=gap/3+1;//保证最后一次gap为1//多路排序并行for(inti=0;i<size-gap;i++){intend=i;inttmp=a[end+gap];while(end>=0&&tmp<a[end])//间距为gap的插入排序{a[end+gap]=a[end];end-=gap;}a[end+gap]=tmp;}}}


3、时间复杂度

时间复杂度在O(N)和O(N*N)之间，大概是O(N^1.25 - 1.6N^1.25)。在初始数组数据已经接近有序时，优化效率最低。