所谓基本有序,就是指小的关键字基本在前面,大的关键字基本在后面,而不大不小的基本在中间....2个元素的数据保持有序,即将第一组数据"3,1,7,5,11,9,15,13"直接插入排序,将其调整为"1,3,5,7,9,11,13,15"的顺序,第二组同理:
然后我们就可以得到如下数组:...然后就是最后一步,我们将数组看作一组,让相邻的两个元素的数据保持有序,即将全组数据直接插入排序,就可以得到最终结果:
至此,其实我们对直接插入排序的优化过程,就是希尔排序算法的思路....它的基本思想是:
先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一组内,并对每一组内的数据进行排序....重复上述分组和排序的工作,当达到gap=1时,所有数据在统一组内排好序.