JavaScript实现插入排序算法之希尔排序算法

热网热热 5评论
前面系列的文章我们以及分享过了插入排序中的直接插入排序,今天再来分享一下插入排序中的希尔排序,通过JavaScript代码实现希尔排序算。
该算法是由希尔(Donald Shell)1959年提出,所以命名为希尔算法。希尔算法是一种插入排序的更高效的改进版本。同时也称递减增量排序算法。

希尔排序思想

先取一个小于待排序数组长度的整数d1作为第一个增量(通常用待排序数组长度的1/2作为第一个增量),把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
希尔排序算法
看概念总是让人脑袋大,在代码中实现并不是真正的要划分成多个数组,只是使用这个增量作为步长,通过步长,来比较值的大小,然后进行直接插入排序。

JavaScript代码实现

function  ShellInsert(R,dk){
var sm;
for(var i = dk; i < R.length; i++){
if(R[i] < R[i - dk]){
sm = R[i];
j = i - dk;
while(j >= 0 && sm < R[j]){
R[j + dk] = R[j];
j = j - dk;
}
R[j + dk] = sm;
}
}
}
function shellsort(R){
for(var i = R.length ; i > 1; i = i/2){
var d = Math.floor(i/2);
 ShellInsert(R,d)
}
}
var a = [9,11,2,8,3,7,12,5,77,3,5,1,0,14]
//var a = [6,5,3,2,1]
shellsort(a)
算法中步长dk的选择,是选择待排序序列的1/2,接下来在选择之前选择步长的1/2,直到步长为1为止。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。

算法分析

增量序列的选择最后一个增量必须为1;
应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
Shell排序的时间性能优于直接插入排序,实验表明,当n较大时,比较和移动的次数约在nl.25到1.6n1.25之间。
算法的空间复杂度分析
算法空间复杂度为O(1)。是一个就地排序。

稳定性

很明显希尔排序是不稳定的。
 

转载请注明觅施南网,JavaScript实现插入排序算法之希尔排序算法:https://www.rewonng.com/qianduanzhishi/151.html

查看剩余内容

相关内容推荐

猜你喜欢内容