有关JS希尔排序算法(详细教程)
程序员文章站
2022-05-04 09:20:26
...
这篇文章主要介绍了JS排序算法之希尔排序与快速排序实现方法,结合实例形式分析了希尔排序与快速排序的原理及javascript实现技巧,需要的朋友可以参考下
本文实例讲述了JS排序算法之希尔排序与快速排序实现方法。分享给大家供大家参考,具体如下:
希尔排序:
定义一个间隔序列,例如是5,3,1。第一次处理,会处理所有间隔为5的,下一次会处理间隔为3的,最后一次处理间隔为1的元素。也就是相邻元素执行标准插入排序。
在开始最后一次处理时,大部分元素都将在正确的位置,算法就不必对很多元素进行交换,这是比插入元素高级的地方。
时间复杂度O(n*logn)
function shellSort(){ var N=arr.length; var h=1; while(h<N/3){ h=3*h+1;//设置间隔 } while(h>=1){ for(var i=h; i<N; i++){ for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){ swap(arr, j, j-h); } } h=(h-1)/3; } } function swap(array, i, j){//两个数调换 var temp =array[j]; array[j]=array[i]; array[i]=temp; }
快速排序:
通过递归的方式将数据依次分解成包含较小元素和较大元素的不同子序列,不断重复这个步骤,直到所有数据都是有序的。
选一个基准值,小于基准值的放一个数组里面。大于基准值的放一个数组里面。
时间复杂度O(n*logn)
function quickSort(arr){ if(arr.length==0){ return []; } var left=[]; var right=[]; var p=arr[0]; for(var i=1; i<arr.length; i++){ if(arr[i]<p){ left.push(arr[i]); }else{ right.push(arr[i]); } } return quickSort(left).concat(p,quickSort(right)); }
上面是我整理给大家的,希望今后会对大家有帮助。
相关文章:
以上就是有关JS希尔排序算法(详细教程)的详细内容,更多请关注其它相关文章!
上一篇: 使用iScroll做出网页内容滚动