做网站非法吗,网站开发语言版本不同,网站开发专业定制,加强网站的建设与管理取一个小于n的整数作为第一个增量#xff0c;把序列分组。所有距离为增量的倍数的元素放在同一个组中。先在各组内进行直接插入排序#xff1b;然后#xff0c;取第二个增量#xff08;第二个第一个#xff09;重复上述的分组和排序#xff0c;直至所取的增量1#…取一个小于n的整数作为第一个增量把序列分组。所有距离为增量的倍数的元素放在同一个组中。先在各组内进行直接插入排序然后取第二个增量第二个第一个重复上述的分组和排序直至所取的增量1即所有元素放在同一组中进行直接插入排序为止。 一般的初次取序列的一半为增量以后每次减半直到增量为1。 以下代码在nodejs中执行通过。 function shellInsertSort(elements, di){//从增量的所在位置开始for(var i di; i elements.length; i){//升序if(elements[i] elements[i-di]){//取出增量位置的元素作为被插入元素哨兵var guard elements[i];var j i - di;elements[i] elements[j];//向前将增量的倍数的位置作为同一组比较及进行直接插入法while(j 0 guard elements[j]){elements[jdi] elements[j];j - di;}//插入elements[j di] guard;}}
}function shellSort(elements){//增量为序列的一半var di parseInt(elements.length / 2);while(di 1){shellInsertSort(elements, di);//每次减半最后增量必须为1di parseInt(di / 2);}
}var elements [10, 9, 8, 7, 6, 5];
console.log(before: elements);
shellSort(elements);
console.log( after: elements); 效率比直接插入法快。但不是一种稳定的排序算法关键取决于增量的选择初次通常选取序列长度的一半。 (转帖):希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))因此中等大小规模表现良好对规模非常大的数据排序不是最优选择。但是比O(n^2)复杂度的算法快得多。并且希尔排序非常容易实现算法代码短而简单。 此外希尔算法在最坏的情况下和平均情况下执行效率相差不是很多与此同时快速排序在最坏的情况下执行的效率会非常差。专家们提倡几乎任何排序工作在开始时都可以用希尔排序若在实际使用中证明它不够快再改成快速排序这样更高级的排序算法. 本质上讲希尔排序算法是直接插入排序算法的一种改进减少了其复制的次数速度要快很多。 原因是当n值很大时数据项每一趟排序需要的个数很少但数据项的距离很长。当n值减小时每一趟需要和动的数据增多此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。在希尔排序开始时增量较大分组较多每组的记录数目少故各组内直接插入较快后来增量di逐渐缩小分组数逐渐减少而各组的记录数目逐渐增多但由于已经按di-1作为距离排过序使文件较接近于有序状态所以新的一趟排序过程也较快。
