希尔排序Shell Sort
- 我们注意到插入排序的比对次数， 在最好的情况下是O(n)， 这种情况发生在列表已是有序的情况下， 实际上， 列表越接近有序， 插入排序的比对次数就越少
- 从这个情况入手， 希尔排序以插入排序作为基础， 对无序表进行“间隔”划分子列表， 每个子列表都执行插入排序
算法思路
- 随着子列表的数量越来越少， 无序表的整体越来越接近有序， 从而减少整体排序的比对次数
- 间隔为3的子列表， 子列表分别插入排序后的整体状况更接近有序
- 最后一趟是标准的插入排序， 但由于前面几趟已经将列表处理到接近有序， 这一趟仅需少数几次移动即可完成
