首页 >web前端 >js教程 >JS实现希尔排序

JS实现希尔排序

不言
不言原创
2018-07-07 17:39:451922浏览

这篇文章主要介绍了关于JS实现希尔排序 ,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下

希尔排序本质上是一种插入排序,但是对数列进行了等间隔分组处理,在每一组中做插入排序,这一优化使得原本 O(n^2)  的时间复杂度一下降为 O(nlogn)。

基本思想

希尔排序是按一定的间隔对数列进行分组,然后在每一个分组中做插入排序;随后逐次缩小间隔,在每一个分组中做插入排序...直到间隔等于1,做一次插入排序后结束。

那么问题来了,间隔应该取多大,怎么缩小?通常我们去取初始间隔为数列长度的一半:gap = length/2,以 gap = gap/2 的方式缩小,下面详细图解整个过程。

原始数组数组如下:

2806437053-5b3da4d90e439_articlex[1].png


首先取间隔为 gap = length/2 = 4,将数组分为如下的4组,对每一组实施插入排序:

196538039-5b3da507911d1_articlex[1].png


第一次排序,每一组较小的元素都移到了相对靠前的位置(这个状态可以叫 n-sorted,即以n为gap分组有序),可以想象相对有序的数组可能更有利于后面的排序。接着继续分组,gap = gap/2 = 2,对每一组实施插入排序:

772152689-5b3da528510d9_articlex[1].png


继续对数组分组,gap = gap/2 = 1,即所有元素组成一组,做插入排序完成算法:

723354304-5b3da547aae7f_articlex[1].png

1394588358-5b3da54b583f3_articlex[1].png

代码实现

内层循环使用的插入排序与普通的插入排序基本一致,只是每次移动的步长变为 gap 而不是 1:

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致,只是每次移动的步长变为 gap
    for(let i = gap; i < arr.length; i++) {
      let j = i;
      let temp = arr[j];
      for(; j> 0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));

以上就是本文的全部内容,希望对大家的学习有所帮助,更多相关内容请关注PHP中文网!

相关推荐:

以上是JS实现希尔排序的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn