突破 O(N^2)：希尔排序
原创约 1369 字
一句话总结
希尔排序是基于 插入排序 的简单改进，通过预处理增加数组的局部有序性，突破了插入排序的 时间复杂度。
你可以点开可视化面板，点击播放按钮，然后点击加速/减速按钮调节速度，即可直观感受希尔排序的过程：
必须承认，希尔排序的思路很难想到，我是在《算法 4》第一次了解到这个算法，然后惊叹于这个算法的简单优化竟然能给插入排序带来如此大的提升。
首先我们要明确一个 h 有序数组 的概念。
h 有序数组
一个数组是 h 有序的，是指这个数组中任意间隔为 h（或者说间隔元素的个数为 h-1）的元素都是有序的。
这个概念用文字不好描述清楚，直接看个例子吧。比方说 h=3 时，一个 3 有序数组是这样的：