这篇文章主要介绍了关于js实现希尔排序 ，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
希尔排序本质上是一种插入排序，但是对数列进行了等间隔分组处理，在每一组中做插入排序，这一优化使得原本 O(n^2) 的时间复杂度一下降为 O(nlogn)。
基本思想
希尔排序是按一定的间隔对数列进行分组，然后在每一个分组中做插入排序；随后逐次缩小间隔，在每一个分组中做插入排序...直到间隔等于1，做一次插入排序后结束。
那么问题来了，间隔应该取多大，怎么缩小？通常我们去取初始间隔为数列长度的一半：gap = length/2，以 gap = gap/2 的方式缩小，下面详细图解整个过程。
原始数组数组如下：
![2806437053-5b3da4d90e439_articlex[1].png](https://img.php.cn//upload/image/363/483/500/1530956331941978.png "1530956331941978.png")
首先取间隔为 gap = length/2 = 4，将数组分为如下的4组，对每一组实施插入排序：
![196538039-5b3da507911d1_articlex[1].png](https://img.php.cn//upload/image/130/582/967/1530956337121802.png "1530956337121802.png")
第一次排序，每一组较小的元素都移到了相对靠前的位置（这个状态可以叫 n-sorted，即以n为gap分组有序），可以想象相对有序的数组可能更有利于后面的排序。接着继续分组，gap = gap/2 = 2，对每一组实施插入排序：
![772152689-5b3da528510d9_articlex[1].png](https://img.php.cn//upload/image/318/313/523/1530956343352313.png "1530956343352313.png")
继续对数组分组，gap = gap/2 = 1，即所有元素组成一组，做插入排序完成算法：
![723354304-5b3da547aae7f_articlex[1].png](https://img.php.cn//upload/image/844/924/998/1530956348685709.png "1530956348685709.png")
![1394588358-5b3da54b583f3_articlex[1].png](https://img.php.cn//upload/image/855/732/590/1530956352630253.png "1530956352630253.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中文网！
相关推荐：
