JS排序算法之希尔算法
希尔算法: 希尔算法在原理上也是一种插入排序,在了解希尔算法之前,必须了解插入排序;
原理: 希尔排序在插入排序的基础上,将数据进行了分组,将原有的数据分为若干个子集,然后对每个子集进行排序,依次类推,不停地分割成子集,直到最后完全排序。
数列:[3,5,2,4,7,6,8,9,1] 先将整个数列以gap为基准进行分割为子集,对子集进行排序;(gap 一般为 Math.floor(arr.length/2)) gap:4 分割后的子集为:3,7 ,1 5,6 2,8 4,9 是个子集 对子集进行排序后:1,3,7 5,6 2,8 4,9 数列为:[1,5,2,4,3,6,8,9,7]
修改gap的值 再次进行排序 gap:2 …….. 直到gap的值为0则停止
JS代码实现:
var arr=[3,5,2,4,7,6,8,9,1]; var gap=Math.floor(arr.length/2); while(gap>0){ for(var i=gap;i<arr.length;i++){ var temp=arr[i]; var j=i-gap; while(j>=0&&arr[j]>temp){ arr[j+gap]=arr[j]; arr[j]=temp; j-=gap; } arr[j+gap]=temp; } gap=Math.floor(gap/2); } 输出结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]
上一篇:
IDEA上Java项目控制台中文乱码