在上一篇博客中，介绍了插入排序的第一种，直接插入排序。再加上前面介绍过的快速排序，冒泡排序和简单选择排序。这四种排序可以不太严谨的定义为八种排序算法中的较简单的排序算法，接下来就要介绍的就是比较复杂的排序算法，所谓的复杂其实指的就是算法的思想上，实现的逻辑上要复杂一些。但是万变不离其宗，大量的代码也许换来的仅仅是很小的效率的提升，但是千里之堤毁于蚁穴，往往是这些小小的细节会赶走大量的用户，这个损失是不可估量的。又说跑题了，回到正题继续介绍今天的主角：希尔排序。
可能大家在看到之前几个排序算法的时候，通过它名字就可以比较形象的猜出这个排序算法的主要特征，甚至是核心的思想。但是今天要介绍的是八大排序算法中唯一一个以发明者的名字命名的排序算法。在物理学，数学中，以科学家名字命名的公式，定义真的是数不胜数，就牛顿牛老师的名字在我学过的知识中就出现了五六次，力的单位牛顿；牛顿一二三定律；牛顿莱布尼茨方程等等。但是可能大家可能没有注意，在计算机领域中，以大师的人名命名的算法包括发明真的是少之又少。“约翰·阿塔那索夫”这个人名可能很多人甚至是同行们都很陌生，简单的介绍一下，这个人是第一个发明现代电子计算机的人，也被成为“电子计算机之父”。我觉得约翰·阿塔那索夫教授所做出的贡献绝对应该和爱迪生，牛顿，瓦特等大师一样被人们牢记，但是甚至对他的名字大家都知之甚少。直到前几年，模仿游戏那部电影上映才让大家认识了“计算机之父”图灵的故事，我觉得这个现象真的很让我困惑。也许甚至是那样伟大的科学家灵魂里也都或多或少具有着一个程序员低调不善言辞的性格吧。
希尔排序，是由Donald Shell于1959年提出的。它作为插入排序的一种，对直接插入排序进行了很大的优化，由于直接插入排序在每次和之前的元素进行比较的时候如果符合条件就要进行插入操作，这样做，如果这样会造成较远的元素需要很多次的无用交换才能放到正确的位置，这样的效率是很低的。 希尔排序会首先比较较远的元素，这样可以使离正确位置很远的元素很快的回到合适的位置。可能有人会问，这不是多此一举吗，正常执行直接插入排序就好了，还多整一步。关于这个疑惑，我举一个简单例子，大家应该就能理解这一步的巧妙之处了。新生报到的时候大家互相不认识，排成一列站队的时候也是高矮胖瘦，参差不齐。这个时候的队列就很像待排序的数组。这个时候老师来了，小个在前大个在后排队，这个时候，比如说队尾站的恰巧是个字很小的同学，如果按直接插入排序的思想的逻辑，老师会从前到后，依次进行排序，当遍历到队尾的时候才会对他进行排序，如果队伍20个人，他就要移动二十次。但是在正常情况下，老师如果发现队尾有一个或几个小个子，会马上把他们叫到前面，把排头几个大个子调到队尾，这就是希尔排序的巧妙之处。接下来就是这个算法的详细介绍和实现。
首先，这个算法引入了一个新的概念，叫做步长。在希尔排序中需要把整个元素分成N组，而这个步长决定着具体分几组，也就是说，哪个元素和距离他长度+步长的元素为一组。举个例子，一个数组：[5,4,3,2,1]，如果步长为3，五个元素步长为3，首先[5,2]一组，[4,1]一组，[3]一组。而分组之后组内进行直接插入排序。组内的元素变为:[2,5],[1,4],[3]。然很关键，将元素复位，[2,1,3,5,4]。然后把步长设为2，[2,3,4]一组，[1,5]一组。最后，将步长设为1的时候，就是我们熟悉的直接插入排序了，前面的步骤的目的就是将较远的元素通过尽可能少的步骤移动到正确的位置，在最后步长为一的时候执行一次直接插入操作，这时的数组基本上只需要移动很少的次数就能实现最终的排序。这就是希尔排序的全部过程，在执行直接插入排序之前，对整个数组进行优化。接下来进行代码实现。
1、设置步长
var step = 1;
var l = arr.length;
while(step<l/3){h=h*3;}
希尔排序和直接插入排序的区别就是引入了步长的概念，步长如何选择就变得很关键了，关于取步长的算法就完全可以长篇大论的讨论很久。这里就不赘述了，鉴于较小的数据量，这里我取步长为：3,1。如果数据量很大，可以将步长设为5，3， 1或者7, 5， 3， 1.这里关于步长的取法就不多说了。
while(step>=1){
for(var i = step;i < l;i++){
for(var j = i;j >= step && arr[j-step] > arr[j];j = j-step){
var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
step = Math.floor(step/3);
}
上面这10行代码其实就是希尔排序的核心实现，可能有的人会觉得似曾相识，和直接插入排序有点像啊。没错，当步长step为1的时候，执行的就是直接插入排序。步长大于1的时候对当前元素和距离加上步长的元素进行比较，如果前面的元素大于后面的元素，那么执行交换操作。然后步长减小，直到步长为1，执行直接插入操作。
这就是希尔排序的全部介绍。感谢阅读。
