希尔排序是插入排序的升级版：

需求：插入排序对于小规模数据来说很好用，但随着数据规模增大，全部遍历并进行插入变得不再现实。

思路：对大规模的数据进行分组，在每个分组内进行插入排序，试图减小每次参与排序的数据规模。

 

用最常用的分组模式 h = 3h +1 来解释一下希尔排序的过程：

假设有20个待排序的数字，用 h = 3h +1 的方式来分组。

用公式确定分组数量大小：

初始值：h = 1

第一趟：h = 3h + 1 = 4

第二趟：h = 3h + 1 = 13

第三趟：h = 3h + 1 = 40（超长，不采纳）

用13作为间隔，进行第一次遍历，并对参与进来的数字进行插入排序：

初始数组：[34, 10, 22, 91, 99, 70, 25, 82, 51, 36, 95, 65, 12, 98, 3, 93, 91, 20, 73, 58]

初次分组：[34, 10, 22, 91, 99, 70, 25, 82, 51, 36, 95, 65, 12, 98, 3, 93, 91, 20, 73, 58]

分组交换：[34, 3, 22, 91, 20, 70, 25, 82, 51, 36, 95, 65, 12, 98, 10, 93, 91, 99, 73, 58]

用4作为间隔，进行第二次遍历，并对参与进来的数字进行插入排序：

初始数组：[34, 3, 22, 91, 20, 70, 25, 82, 51, 36, 95, 65, 12, 98, 10, 93, 91, 99, 73, 58]

二次分组：[34, 3, 22, 91, 20, 70, 25, 82, 51, 36, 95, 65, 12, 98, 10, 93, 91, 99, 73, 58]

分组交换：[12, 3, 10, 58, 20, 36, 22, 65, 34, 70, 25, 82, 51, 98, 73, 91, 91, 99, 95, 93]

最后用1作为间隔，得到最终的结果：

最后交换：[3, 10, 12, 20, 22, 25, 34, 36, 51, 58, 65, 70, 73, 82, 91, 91, 93, 95, 98, 99]

 

将上述过程翻译成代码：

function shellSort(arr){　　//根据公式获取随机数列　　var h = 1;　　var len = arr.length;　　while(h
     
      0;h = Math.floor(h/3)){　　　　var preIndex,current;　　　　for(var i=h;i
      
       = 0 && arr[preIndex]>current){　　　　　　　　arr[preIndex+h] = arr[preIndex];　　　　　　　　preIndex -= h;  　　　　　　}　　　　　　arr[preIndex+h] = current;　　　　}　　} }