一.优化直接插入排序算法
我们在之前对直接插入排序算法的优化部分通过对直接插入排序的分析可以得到一个结论,即:
进行直接插入排序的数组,如果越接近局部有序,则后续进行直接插入排序算法时其时间复杂度就会越低...例如下面这个数组序列,虽然它还是无序的状态,甚至是局部逆序的状态,但至少它的前8个数据"0-7"都在前半部分,后8个数据"8-15"都在后半部分,这样就比完全逆序状态更接近基本有序,相应的算法执行的次数也直接减少了一半...然后无论这次有没有交换位置,都将tmp赋值给a[end+gap]的位置,如果没有交换,则a[end+gap]就是tmp原本的值,如果这次有交换,则因为end减去了gap,则会使tmp赋值给原本a[end...还有人在大量的实验基础上推出:当n在某个特定范围内,希尔排序所需的比较和移动次数约为
,当
时,可减少到
。...——《数据结构-用面向对象方法与C++描述》殷人昆
因此,当前对于希尔排序的时间复杂度,学术界仍没有一个确切的研究结果,我们只能在估算希尔排序时间复杂度时借助Knuth大佬的实验统计结果