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可修改的性能;


AXIHE / 精选资源

浏览全部教程

面试题

学习网站

前端培训
自己甄别

前端书籍

关于朱安邦

我叫 朱安邦,阿西河的站长,在杭州。

以前是一名平面设计师,后来开始接接触前端开发,主要研究前端技术中的JS方向。

业余时间我喜欢分享和交流自己的技术,欢迎大家关注我的 Bilibili

关注我: Github / 知乎

目前重心已经放在研究区块链上面了

我叫朱安邦,阿西河的站长

目前在杭州从事区块链周边的开发工作,机械专业,以前从事平面设计工作。

2014年底脱产在老家自学6个月的前端技术,自学期间几乎从未出过家门,最终找到了满意的前端工作。更多>