,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次
是否能够减少这样的移位呢?...希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
初始时,有一个大小为 10 的无序序列...这样相隔距离为 1 的元素组成一组,即只有一组
按照直接插入排序的方法对每个组进行排序。此时,排序已经结束
演示
1.增量N/2=4分组
?...(即,步长gap)的选取有关
{1,2,4,8,...}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n²)
Hibbard提出了另一个增量序列{1,3,7,...,2^k...-1},这种序列的时间复杂度(最坏情形)为O(n^1.5)
Sedgewick提出了几种增量序列,其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,...}
9×4