shell sort是对insertion sort(插入排序)的一个改进。先来看几个概念。

##概念

倒置指的是数组中的两个顺序颠倒的元素，比如EXAMPLE中有11对倒置：E-A, X-A, X-M, X-P, X-L X-E, M-L, M-E, P-L, P-E, L-E。如果数组中倒置的数量小于数组大小的某个倍数，那么我们说这个数组是部分有序的。

下面是几种典型的部分有序的数组：

• 数组中每个元素距离它的最终位置都不远
• 一个有序的大数组接一个小数组
• 数组中只有几个元素的位置不正确

插入排序对这样的数组很有效。当倒置的数量很少时，插入排序可能比任何排序算法都要快。

h有序数组：给定一个包含n个元素的数组a，若对于任意一个满足h <= i <= n的i，都有a[i-h] <= a[i]，那就说数组h有序。

直观上来看，h有序数组是由多个有序的数组穿插在一起形成的。有序的数组是h=1时的特例。

对于大规模乱序数组，插入排序很慢。假设数组中最大的元素在数组的最左边，在插入排序中，此元素在每一轮排序都会向右移动一个位置，直到最后一轮才会移动到正确的位置(最右边)。也就是说，若一个元素在其正确位置左边x个位置，那么需要x次移动才能将其移动到正确位置。对于大数组，这是非常低效的。

希尔排序(Shell sort)给予元素一次移动很大距离的能力。Shell sort首先将数组成为h有序(h较大)，然后不断减少h的值，直到h = 1。

希尔排序更高效的原因是，它权衡了子数组的规模和有序性。排序之初，各个子数组都很短；排序之后子数组都是部分有序的，这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。

和选择排序以及插入排序形成对比的是，希尔排序也可以适用于大型数组。有经验的程序员有时会选择希尔排序，因为对中等大小的数组它的运行时间是可以接受的。它代码量很小，且不需要使用额外的内存空间。其他更高校的算法，除了对于很大的N，可能只比希尔排序快2倍，而且更复杂。如果你需要一个排序算法，又没有系统排序函数可用(例如直接接触硬件、嵌入式系统)，可以先用希尔排序，再考虑是否需要将其替换为更高效、复杂的排序算法。

最开始，我们将h设为一个较大但小于数组长度的值，使得间隔为h的子数组里只有2个元素。