阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      JavaScript 常见算法

      JS中的常见算法

      • 插入排序
      • 冒泡排序
      • 快速排序

      常见操作数组的

      • 数组去重复
      • 从一个长度10万的数组中,随机取出100条数据(取出的数据不能重复);

      JS中的常见算法


      插入排序

      插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

      操作步骤:首先选取数组的第一项即ary[0],我们可以认为这个数是已经安排好序的,再取ary[1]项插入到已经排好序的元素中,此时只有ary[0],我们比较ary[0]和ary[1];大于ary[0]就放在后面,小于就插到ary[0]前面;要插入的元素依次为ary[1]至ary[ary.leng-1]项;插入到排序好的数组中的时候,插入每一项都需要从后面往前面遍历已经排序好的元素;

      如果排序好的元素比插入的元素大,则把该元素往后挪一位,知道已经排序的元素小于等于要插入的元素(或者已经遍历完已经排好序的数组项),则把要插入的元素放在该位置+1的索引位置中(反向排的时候,需要放在数组的第0个位置),对每个插入的元素都执行上面的操作,最终数组就是排序好的;

      有BUG的写法;

          var ary=[11,2,31,45,6,78,37,33,21];
      
          function insertSort(ary){
              var temp;//定义一个临时变量,保存要插入的值;
              for(var i= 1,len=ary.length;i<len;i++){
                  if(ary[i]<ary[i-1]){
                      temp=ary[i];
                      ary[i]=ary[i-1];
                      ary[i-1]=temp;
                  }
              }
              return ary;
          }
          var newAry=insertSort(ary);
          console.log(newAry);//[2, 11, 31, 6, 45, 37, 33, 21, 78]
      

      因为只把小的数往前移动了一次;这里需要用到while循环,把6移动2后面;

          var ary=[11,2,31,45,6,78,37,33,21];
      
          function insertSort(ary){
              var temp;//定义一个临时变量,保存要插入的值;
              for(var i= 1,len=ary.length;i<len;i++){
                  if(ary[i]<ary[i-1]){
                      temp=ary[i];//需要插入的值;
                      var pIndex=i-1;//需要插入值的前一个索引;
                      while(temp<ary[pIndex]&&pIndex>=0){
                          ary[pIndex+1]=ary[pIndex];//相当于ary[i]=ary[i-1];
                          ary[pIndex]=temp;//相当于ary[i-1]=temp;完成一波交换;
                          pIndex--;//准备下一波交换;
                      }
                  }
              }
              return ary;
          }
          var newAry=insertSort(ary);
          console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
      

      冒泡排序

      基本思想:就是把数据像泡泡一样网上冒,让体积最轻的泡泡浮在最上面,然后按照重量往下依次排列;

      冒泡排序的操作原理

          var ary=[11,2,31,45,6,78,37,33,21];
      

      用循环的方式,循环数组的长度,然后比较数组的数据

      • 第一次循环把ary的最大值放在ary[ary.length-1]的位置;
        • ary[0]>ary[1],如果是true,说明第一项比第二项大,交换ary[0]和ary[1]的位置;如果是false则不改变位置;
        • ary[1]>ary[2],如果是true,说明第二项比第三项大,交换ary[1]和ary[2]的位置;如果是false则不改变位置;(此时的ary[1]肯定比ary[0]大的,因为开始的时候已经把ary[0]和ary[1]比较了)
        • ……
        • ary[ary.length-2]>ary[ary.length-1];比较到这个时候,ary[ary.length-1]的位置肯定是最大的数据了;
      • 第二次循环,把倒数第二大的数据,放在数组的ary[ary.length-2]位置;
        • 备注:第二次循环的时候,只需要比较到ary[ary.length-2]的位置就可以了,因为ary[ary.length-1]已经是最大值了,无需再次比较;

      注意:交换位置的时候,需要一个中间变量来协助,假设让a和b进行数据交换; var temp=a;a=b;b=temp; 这样就可以把a和b的数据交换好了;

          var ary=[11,2,31,45,6,78,37,33,21];
      
          function sortAry(ary){
              var aryLen=ary.length;//获取数组的长度;有aryLen个数在排序;
              var temp=null;//临时变量,交换数据中用的
              for(var i= 0,iLen=aryLen-1;i<iLen;i++){//外层循环n-1次;
                  for(var j= 0,jLen=aryLen-1-i;j<jLen;j++){//每次循环完,都能从剩下的数组中找出个最大的数组放在aryLen-1-i的位置;
                      if(ary[j]>ary[j+1]){
                          temp=ary[j];
                          ary[j]=ary[j+1];
                          ary[j+1]=temp;
                      }
                  }
              }
              return ary;
          }
      
          var newAry=sortAry(ary);
          console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
      

      避免无效循环的方法;

          var ary=[11,2,31,45,6,78,37,33,21];
      
          function sortAry(ary){
              var aryLen=ary.length;//获取数组的长度;有aryLen个数在排序;
              var temp=null;//临时变量,交换数据中用的
              var flag=false;//设置标志位,初始化为false
              for(var i= 0,iLen=aryLen-1;i<iLen;i++){//外层循环n-1次;
                  for(var j= 0,jLen=aryLen-1-i;j<jLen;j++){//每次循环完,都能从剩下的数组中找出个最大的数组放在aryLen-1-i的位置;
                      if(ary[j]>ary[j+1]){
                          temp=ary[j];
                          ary[j]=ary[j+1];
                          ary[j+1]=temp;
                          flag=true;//如果交换好了,做个标记,避免无效的循环;
                      }
                  }
                  if(!!flag){//只要交换了位置,flag的值就重新设置为false了;
                      flag=false;
                  }else{//如果没有交换,说明数组已经排好序了,可以结束循环了;
                      break;
                  }
              }
              return ary;
          }
      
          var newAry=sortAry(ary);
          console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
      

      冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

      算法步骤:

      • 1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。
      • 2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
      • 3)针对所有的元素重复以上的步骤,除了最后一个。
      • 4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

      快速排序;

      基本思想:首先从数组ary选取一个基准点(通常我们取中间项作为基准点),然后遍历数组,把小于基准项放到基准点左边集合,把大于基准项放在基准点右边集合;然后对左边和右边两个集合分别再重复前面的操作;(直到每个集合就剩下一个元素的时候),其实就是一个递归的思想

      操作步骤

          var ary=[11,2,31,45,6,78,37,33,21];
      

      依旧拿上边这个数组做例子,,我们确定一个基准点,

          var ary=[11,2,31,45,6,78,37,33,21];
          var pivot=ary[Math.floor(ary.length/2)];
          console.log(pivot);//6
      

      然后我们循环数据中的剩余项,把小于6的放在数组left中,把大于等于56的数组项放在数组right中,第一轮操作结束后left=[2],right=[11,31,45,78,37,33,21]

      然后对left重复以上的操作,直到left和right仅剩一项或者空时候结束,最终返回left+pivot+right;

          var ary=[11,2,31,45,6,78,37,33,21];
      
          function quickSort(ary){
              var aryLen=ary.length;//获取ary的长度;
              if(aryLen<=1){//如果ary小于等于1的长度,就直接返回了;这一步非常重要,是判断是否循环完的标志;
                  return ary;
              }
              var pINdex=Math.floor(ary.length/2);//基准项的所引值
              var pivot=ary.splice(pINdex,1);//删除基准项,并把基准项赋值给pivot;
              var left=[],right=[];
              for(var i= 0,len=ary.length;i<len;i++){
                  if(ary[i]<pivot[0]){
                      left.push(ary[i]);
                  }else{
                      right.push(ary[i])
                  }
              }
              return quickSort(left).concat(pivot,quickSort(right));
          }
          var newAry=quickSort(ary);
          console.log(newAry);//[2, 6, 11, 21, 31, 33, 37, 45, 78]
      

      常见操作数组的


      数组去重;

      • 第一种方法:每一次拿出数组中的当前项和后面的所有项进行比较,如果相同的话,删除即可;

         var ary=[1,2,34,56,6,7,45,3,2,2,12,4,9,8,6,7,4];
         function deleteRepeat(ary){
             for(var i= 0,len=ary.length-1;i<len;i++){//比较length-1次;
                 var temp=ary[i];
                 for(var j=i+1;j<ary.length;j++){
                     if(temp==ary[j]){
                         ary.splice(j,1);
                         j--;//删除以后需要把j重置下,避免数组塌陷;
                     }
                 }
             }
             return ary;
         }
         var newAry=deleteRepeat(ary);
         console.log(newAry);
        

      这种处理方法,处理少量数据的时候没有问题的,但是做很多数组的时候,性能就是一个很大的问题了,双重循环毕竟还是有优化的空间的,通常用第二种方法;

      第二种方法:利用对象的属性名和属性值不能重复的原理,把数组中每一项的值当作对象的属性名属性值进行储存,在每一次储存之前进行判断,如果对象中已经存在这一项,我们就删除数组中这项,不存在我们就把这一项储存到我们的新的对象中,(注意对象在这里只是一个临时储存的作用),在处理完成后最好置为null;养成好习惯 ;

          var ary=[1,2,34,56,6,7,45,3,2,2,12,4,9,8,6,7,4];
          function deleteRepeat(ary){
              var obj={};
              for(var i= 0,len=ary.length;i<len;i++){
                  var temp=ary[i];
                  if(obj[temp]==temp&&temp!=undefined){
                      ary.splice(i,1);
                      i--;
                      continue;
                  }
                  obj[temp]=temp;
              }
              obj=null;
              return ary;
          }
          var newAry=deleteRepeat(ary);
          console.log(newAry);
      

      从一个长度10万的数组中,随机取出100条数据(取出的数据不能重复);

      原理:随机获取100个索引,每一次获取的时候,都把对应的项获取,为了避免数组中的项重复,每获取一个就把原有数组中的这一项删除;

      为了方便掩饰从20个里取5个随机数;

      第一种比较耗性能的写法;

          var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
          function selectOption(ary,optionNumber){
              var targetAry=[];
              if(!optionNumber){
                  console.log("请指定需要删选的数量!");
              }
              for(var i=0;i<optionNumber;i++){
                  var ran=Math.round(Math.random()*(ary.length-1));//获取0-数组最大索引的一个随机数;
                  targetAry.push(ary[ran]);//按照获取的随机索引,把对应的值取出来,放到新书组中;
                  ary.splice(ran,1);//数组中实现删除的时候比较耗性能,为了牵扯到数组长度的改变,数组被删除的项,后面所有数据都前进一位;
              }
              return targetAry;
          }
          var newAry=selectOption(ary,2);
          console.log(newAry);
      

      确定在代码后面已经说明,这种的比较耗性能;

          var ary=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
          function selectOption(ary,optionNumber){
              var targetAry=[];
              if(!optionNumber){
                  console.log("请指定需要删选的数量!");
              }
              for(var i=0;i<optionNumber;i++){
                  var ran=Math.round(Math.random()*(ary.length-1));//获取0-数组最大索引的一个随机数;
                  targetAry.push(ary[ran]);//按照获取的随机索引,把对应的值取出来,放到新书组中;
                  ary[ran]=ary[ary.length-1];//把数组最后一项放到当前要删除索引的这一项;
                  ary.length=ary.length-1;//删除最后一项;
              }
              return targetAry;
          }
          var newAry=selectOption(ary,10);
          console.log(newAry);
      

      这种的写法,是操作数组的常用处理方式;借助数组length可修改的性能;

      目录
      目录