【JavaScript算法】---希尔排序
标签：var 情况 javascrip while 增量 bsp item 数组 增量排序
一、什么是希尔排序
希尔排序(Shell‘s Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
思路：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
逻辑：
在希尔排序中最重要的是分组，我们先找到一个间隔，每隔一定的间隔将这些数字排位一组，
假设有这样一个数组 [9,1,2,5,7,4,8,6,3,5] ;我们每隔5个为一组。那么这个数组被我们分成了以下几组
第一组：9 4
第二组：1 8
第三组：2 6
第四组：5 3
第五组：7 5
分组完毕后我们在每隔组的组内进行排序
第一组： 4 9
第二组：1 8
第三组 2 6
第四组 3 5
第五组 5 7
排序后我们在将这个数组重新设间隔重新进行排序(下一次的间隔减半) 2个为一组
[4,1,2,3,5,9,8,6,5,7]
第一组：4 2 5 8 5 ==》组内排序 2 4 5 5 8
第二组：1 3 9 6 7 ==》组内排序 1 3 6 7 9
2 1 4 3 5 6 5 7 8 9
排序后我们在将这个数组重新设间隔重新进行排序(下一次的间隔减半) 1个为一组最后一次也就是两两比较
1 2 3 4 5 5 6 7 8 9
注意：间隔在希尔排序中一般是没有特别的规定，通常情况下是数组长度的一半
二、代码
var arr = [2,5,1,9,0]
//算间隔
var len = Math.floor(arr.length/2)
while(len>0){
for(var i=len;i){
var temp = arr[i];
for(var j=i-len;j>=0&&templen){
arr[j+len] = arr[j]
}
arr[j+len] = temp;
}
len = Math.floor(len/2)
}
【JavaScript算法】---希尔排序
标签：var 情况 javascrip while 增量 bsp item 数组 增量排序
原文地址：https://www.cnblogs.com/nanianqiming/p/9541647.html
评论