原理：
希尔排序是直接插入排序的一种改进算法，但更为有效，大体想法就是先将整体数据变得更为有序，使得直接插入时效率更好，最后形成一个有序的整体。这里有一个步长的概念，假设它是dt。我们这里可以把它想成分组，每次都分出来dt个组，然后对每组进行直接插入排序，dt逐渐变小的，变小的方式不固定，通常是以一个数学函数的方式来变小，大多数的就是每次对dt折半，直到dt等于1结束，这就说明最后就变成一个组，而且他相对有序，一次直接插入算法就搞定了。
我们假设一组数据：2，3，5，7，8，9，1，4。按升序排列。
- 最开始步长就取长度的一半，4。那分组是怎样分的呢？因为4是步长，所以第一个数据2就和它位置加4的数据，也就是8为同一组。同理，(3, 9)，(4, 1)，(7, 4)各为一组，然后每组进行一次直接插入排序，所以数据就变成了2，3，1，4，8，9，5，7。
- 进行完一次之后就要调整dt的大小，应用一个数学函数，我们这里就把它定位折半，也就是除以2，那么dt就等于2，再以2为步长分组。(3,4,9,7)，(2,1,8,5)各为一组，在进行直接插入排序，数据就变成了1，3，2，4，5，7，8，9。看，数据基本已经有序了。我们只需要再来最后一次就可以了。
- 继续调整dt大小，dt＝dt／2，所以dt等于1，最外层循环终止，所以数据为一个大组，排序后为1，2，3，4，5，7，8。
看完这个例子应该明白一些了吧，下面看完算法将更加简单明了。
算法：
int dt, temp;
for(dt = Array.length / 2;dt >= 1;dt = dt / 2) {
for(int i = dt;i < Array.length;i++) {
if(Array[i] > Array[i - dt]) {
temp = Array[i - dt];
for(int j = i;j > 0 && temp < Array[j - 1];j--) {
Array[j] = Array[j - 1];
}
Array[j] = temp;
}
}
}
稳定性：
希尔排序是不稳定的，假设数据为3，2，2。第一次排序后就变为了2，2，3。两个同值元素相对位置改变。
复杂度：
希尔排序的复杂度并不好计算，当对dt步长计算的函数不固定时，他的时间复杂度也不确定，而取dt是多少为最合适的，这要取决于数据，因此时间复杂度无法准确计算，不过有一个范围，最差就是o(n^2)，最好据查证是o(n^1.3)。依据不同增量函数而不同。空间复杂度就是o(1)。
优缺点：
希尔排序是肯定好于直接插入排序的，但其不稳定性导致有可能在数据中出现一些未知差错。效率高，代码短小，易于实现，适合中小规模数据排序。
测试：
测试数据100000个，平均排序时间4910 ms左右。
PS：算法的代码都是伪代码，不同语言写法不同。测试环境为，代码语言Javascript，处理器 双核 2.6 GHz Intel Core i5。