希尔排序--学习笔记

2018-06-24 02:10:30来源：未知阅读 ()

　　希尔排序（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排序就是一个插入排序。

代码实现

 1 var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73];
 2 var shellSort = function(array) {
 3     var temp;
 4     var gap = Math.floor(array.length/2);
 5     for(gap;  gap > 0; gap = Math.floor(gap/2)) {
 6         for(var i = gap; i < array.length; i++) {
 7             temp = array[i];
 8             for(var j = i; j >= gap && temp-array[j-gap] < 0; j -= gap) {
 9                 array[j] = array[j - gap];
10             }
11             array[j] = temp;
12         }
13     }
14     return array;
15 };
16 console.log(shellSort(s));
17 //=>[ 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，就变成了一个纯粹的插入排序：

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

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

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

 1 var s = [21, 3, 36, 81, 12, 7, 23, 48, 62, 95, 44, 73];
 2 var shellSort = function(array, gap) {
 3     var temp;
 4     for(var i = gap; i < array.length; i++) {
 5         temp = array[i];
 6         for(var j = i; j >= gap && temp - array[j - gap] < 0; j -= gap) {
 7             array[j] = array[j - gap];
 8         }
 9         array[j] = temp;
10     }
11     return array;
12 };
13 var h4 = shellSort(s, 4);
14 console.log(h4);
15 var h2 = shellSort(h4, 2);
16 console.log(h2);
17 var h1 = shellSort(h2, 1);
18 console.log(h1);
19 //=>[ 12, 3, 23, 48, 21, 7, 36, 73, 62, 95, 44, 81 ]　　//4排序后
20     [ 12, 3, 21, 7, 23, 48, 36, 73, 44, 81, 62, 95 ]　　//2排序后
21     [ 3, 7, 12, 21, 23, 36, 44, 48, 62, 73, 81, 95 ]　　//1排序后