希尔排序算法及分析

希尔排序Shell Sort

• 我们注意到插入排序的比对次数， 在最好的情况下是O(n)， 这种情况发生在列表已是有序的情况下， 实际上， 列表越接近有序， 插入排序的比对次数就越少
• 从这个情况入手， 希尔排序以插入排序作为基础， 对无序表进行“间隔”划分子列表， 每个子列表都执行插入排序

算法思路

• 随着子列表的数量越来越少， 无序表的整体越来越接近有序， 从而减少整体排序的比对次数
• 间隔为3的子列表， 子列表分别插入排序后的整体状况更接近有序
• 最后一趟是标准的插入排序， 但由于前面几趟已经将列表处理到接近有序， 这一趟仅需少数几次移动即可完成