希尔排序--学习笔记

希尔排序（Shellsort）由Donald Shell提出，对直接插入排序进行了改进。由于其算法特征，又叫做"缩减增量排序"。

希尔排序使用一个增量序列（h₁, h₂, h₃, ..., h_k），只要h₁ = 1，任何增量序列都是可行的，增量序列不唯一，但有的增量序列比另一些增量序列要好。希尔排序的一个重要性质是，一个h_k排序的文件保持它的h_k排序性。其中，一趟h_k排序的作用就是对h_k个独立的子数组分别执行一次插入排序。（摘自《算法和数据结构》）

算法分析

概念总是显得有点深奥，从例子去分析：

假设我们有一个数组：

var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73]；

选择一个增量序列h₁=1，h₂=2，h₃=4。

1.执行一次4排序：将原数组分为四个独立的子数组，对四个子数组进行插入排序，

①将黄色数组排序，其他不变

②同理

③同理

④同理

2.继续执行2排序：将4排序后的数组分为两个独立的子数组，分别进行插入排序，

①将黄色部分排序

②同理

3.最后进行1排序：将整个数组进行一次插入排序，

此时，数组已经排序。

由此看来，希尔排序就是若干个插入排序，只不过一个hk排序改变了不止一个数的位置（因为一个h_k排序包含了h_k个插入排序），而插入排序一趟只能将数据移动以为。1排序就是一个插入排序。

代码实现

var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73];
 var shellSort = function(array) {
     var temp;
     var gap = Math.floor(array.length/2);
     for(gap;  gap > 0; gap = Math.floor(gap/2)) {
         for(var i = gap; i < array.length; i++) {
             temp = array[i];
             for(var j = i; j >= gap && temp-array[j-gap] < 0; j -= gap) {
                 array[j] = array[j - gap];
             }
             array[j] = temp;
         }
     }
     return array;
 };
 console.log(shellSort(s));
 //=>[ 3, 7, 12, 21, 23, 36, 44, 48, 62, 73, 81, 95 ]

代码参考自《算法和数据结构》。

第5行for为增量序列的选取，采用shell建议的h_k=N/2（向下取整）；

第6~12行为插入排序的代码，很巧妙，将第5行的for去掉，将gap值改为1，就变成了一个纯粹的插入排序：

var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73];
 var shellSort = function(array) {
     var temp;
     for(var i = 1; i < array.length; i++) {
         temp = array[i];
         for(var j = i; j >= 1 && temp - array[j - 1] < 0; j -= 1) {
             array[j] = array[j - 1];
         }
         array[j] = temp;
     }
     return array;
 };
 console.log(shellSort(s));
 //=>[ 3, 7, 12, 21, 23, 36, 44, 48, 62, 73, 81, 95 ]

这也说明了1排序就是一个插入排序，也是h_k序列必须包含h_k=1的原因。

另外，为了在学习过程中更好地观察每个h_k排序的结果，我把代码修改如下，其中shellSort还接受一个h_k：

var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73];
 var shellSort = function(array, gap) {
     var temp;
     for(var i = gap; i < array.length; i++) {
         temp = array[i];
         for(var j = i; j >= gap && temp - array[j - gap] < 0; j -= gap) {
             array[j] = array[j - gap];
         }
         array[j] = temp;
     }
     return array;
 };
 var h4 = shellSort(s, 4);
 console.log(h4);
 var h2 = shellSort(h4, 2);
 console.log(h2);
 var h1 = shellSort(h2, 1);
 console.log(h1);
 //=>[ 12, 3, 23, 48, 21, 7, 36, 73, 62, 95, 44, 81 ]　　//4排序后
     [ 12, 3, 21, 7, 23, 48, 36, 73, 44, 81, 62, 95 ]　　//2排序后
     [ 3, 7, 12, 21, 23, 36, 44, 48, 62, 73, 81, 95 ]　　//1排序后

总结

1.希尔排序是通过一个增量序列来将数组元素调整到一个"比较有序"的状态，最后对整个最数组进行一次插入排序（1排序）。有可能在1排序前数组就以排序，这样1排序只需要线性时间；也有可能前面的h_k排序并没有改变数组的序列，从而1排序时花费很多的时间。

2.增量序列的选择不是唯一的，存在更具排序效率的增量序列。

---------------------------------------------------------------------------------

本文为个人学习随笔，仅供个人学习，如有雷同，敬请原谅。