首页 > web前端 > js教程 > 有关JS希尔排序算法(详细教程)

有关JS希尔排序算法(详细教程)

亚连
发布: 2018-06-21 11:29:00
原创
1781 人浏览过

这篇文章主要介绍了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));
}
登录后复制

上面是我整理给大家的,希望今后会对大家有帮助。

相关文章:

在javaScript中有关空值和假值的说法

在Webpack中有关自动化构建(详细教程)

在微信小程序中如何实现图片上传等一系列功能

如何搭建前端通用的数据模拟框架(详细教程)

以上是有关JS希尔排序算法(详细教程)的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板