例如,在对一组人按出生日期排序时,如果有两个人出生日期相同,我们可能会希望他们在排序后保持按姓名的顺序,如果使用稳定的排序算法,就可以保证这一点。...,然后逐渐减少子列表的数量,使整个列表趋向于部分有序,**最后当整个列表作为一个子列表进行插入排序时,由于已经部分有序,所以排序效率高。...**这个过程中,每次排序的子列表是通过选择不同的“增量”来确定的。
实现思路:
预排序
直接插入排序
预排序:
根据当前增量,数组被分为若干子序列,这些子序列的元素在原数组中间隔着固定的增量。...所以我们有如下子序列:
子序列1: 9, 6, 3, 0
子序列2: 8, 5, 2
子序列3: 7, 4, 1
然后对每个子序列进行独立的插入排序:
子序列1排序后:0, 3, 6, 9
子序列2排序后...:2, 5, 8
子序列3排序后:1, 4, 7
现在将排序后的子序列放回原数组中,数组变化为:
完成了一轮希尔排序,此时整个数组并不完全有序,但是已经比原始的数组更接近有序了。