具体希尔排序和插入排序的过程网上有不少，这里就不多说了。下面只谈个人对希尔排序为什么能突破O(n^2)的理解。
希尔排序算法之所以比插入排序法好，是因为它的“大跨步”比较。
首先，希尔排序是插入排序的改进。插入排序的的过程就是识别“逆序数”，并将其两两交换，直至“逆序数”不存在的过程，可以理解为逆序数两两交换是插入排序和希尔排序的元操作。
这里，在两个数的最终排序中，其顺序与现在的顺序不同的两个数。
只要在排序的过程中，逆序数是在不断消减的，就可以认为是在做“有用功”。
假如希尔排序所取的间隔为10，相比插入排序法需要10次交换逆序数，希尔排序只要一次，所以就省下了不少次数。而希尔排序的后续过程，就是把这个序列进一步有序化，不断减少逆序数。
因此希尔排序间隔大于1时，其消减逆序数的效率总是大于插入排序的。
标签：10,定性分析,插入排序,希尔,排序,过程,序数 From： https://www.cnblogs.com/chase-the-light/p/16882403.html