希尔排序--学习笔记

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

新老客户大回馈,云服务器低至5折

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

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

算法分析

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

  假设我们有一个数组:

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

  选择一个增量序列h1=1,h2=2,h3=4。

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

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

  ②同理

  ③同理

  ④同理

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

  ①将黄色部分排序

  ②同理

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

  此时,数组已经排序。

  由此看来,希尔排序就是若干个插入排序,只不过一个hk排序改变了不止一个数的位置(因为一个hk排序包含了hk个插入排序),而插入排序一趟只能将数据移动以为。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建议的hk=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排序就是一个插入排序,也是hk序列必须包含hk=1的原因。

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

 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排序后

 

 

总结

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

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

 

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

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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Uncaught ReferenceError: Vue is not defined 当出现这个问题

下一篇:Angular使用总结 --- 搜索场景中使用rxjs的操作符