频道栏目
首页 > 程序开发 > web前端 > JavaScript > 正文
讲述js算法中的排序、数组去重
2013-10-17 16:23:32           
收藏   我要投稿
其实在js中实现数组排序,采用数组中sort方法实现还是比较简单的:

一 排序

简单实现数组排序

[javascript] 

var arr = [];  

for(var i=0;i<20;i++){  

    arr.push(Math.floor(Math.random()*100))  

}  

arr.sort(function(a,b){  

    return a>b?1:-1;  

})  

alert(arr)  

 

 

 

不能简单使用sort方法,默认情况下 sort方法是按ascii字母顺序排序的,而非我们认为是按数字大小排序,

sort() 方法可以接受一个 方法为参数 ,这个方法有两个参数。分别代表每次排序比较时的两个数组项。sort()排序时每次比较两个数组项都回执行这个参数,并把两个比较的数组

项作为参数传递给这个函数。当函数返回值为1的时候就交换两个数组项的顺序,否则就不交换。

 

算法的数组排序

[javascript] 

var arr = [];  

for(var i=0;i<20;i++){  

    arr.push(Math.floor(Math.random()*100))  

}  

//生成一个无序的arr数组  

function sort(arr,start,end){  

    //数组长度为1  

    if(start == end ){  

        return [arr[start]]  

    }else if(start == end-1){  

        //数组长度为2,根据数值大小 来排序  

        if(arr[start]>arr[end]){  

            return [arr[end],arr[start]]  

        }else{  

            return [arr[start],arr[end]]  

        }  

    }  

    // 数组长度一半  

    var l = Math.floor((start+end)/2);  

    //左边数组  

    var arrLeft = sort(arr, start,l);  

    //右边数组  

    var arrRight = sort(arr,l+1,end);  

    //返回结果  

    var result = [];  

    //分割成两部分 左右两个数组 只比对数组中的第一个数,那个数值小就把谁放到结果里面,并把小的数值删除掉,固采用数组中的shift方法。一旦出现左边数组或右边数组,没有数据的时候  

    //result数组就与还有数据的数组合并 采用 concat,并返回结果  

    while(arrLeft.length>0 || arrRight.length>0){  

        if(arrLeft.length==0){  

            result = result.concat(arrRight);  

            break;  

        }else if(arrRight.length==0){  

            result = result.concat(arrLeft);  

            break;  

        }  

        if(arrLeft[0]<arrRight[0]){  

            result.push(arrLeft.shift())  

        }else{  

            result.push(arrRight.shift());  

        }  

    }  

    return result;  

}  

var arrSort = sort(arr,0,arr.length-1);//参数 数组,开始位置,结束位置  

  

document.write(arr+'<br/>'+arrSort);  

 

讲解:数组排序主要是采用将数组一拆为二,直到不能为之,最后只能是拆掉数组里面只能是一个或者是两个,因为数组的长度有奇数偶数之分,拆到最后 数组里面只有一个或者两个之后 开始排序并返回结果,并将这些结果在一一比对 进行合并。这个方法 可能大家觉得 为什么要这么复杂,一直采用第一种不行吗,其实当然可以啦,但是这个世界上还有性能这个词汇,当数据之后几个 几十个 几个百 ,大家的算出的结果时间是没有什么区别的 ,如果当数据庞大的几亿 几十亿 我们还有这种自信用第一种方法吗,其实js的算法就是分而治之,将很多问题划分成小的来解决。

二、数组去掉重复

简单方法去掉重复:先声明一个空的数组,将重复的数组 for 循环插入,重复的跳过 不重复的插入

[javascript] 

var arr = [];  

for(var i=0;i<20;i++){  

    arr.push(parseInt(Math.random()*10));  

}  

Array.prototype.indexOf = function(n){  

    for(var i=0;i<this.length;i++){  

        if(this[i] == n){  

            return i;  

        }  

    }  

    return -1;  

}  

function removeDup(arr){  

    var result = [];  

    for(var i=0;i<arr.length;i++){  

        if(result.indexOf(arr[i]) == -1){  

  

            result.push(arr[i]);  

        }  

    }  

    return result;   

}  

var arr2 = removeDup(arr)  

document.write(arr+'<br/>'+arr2)  

 

 

算法数组去掉重复

[javascript] 

var arr = [];  

for(var i=0;i<20;i++){  

    arr.push(parseInt(Math.random()*10));  

}  

Array.prototype.indexOf = function(n){  

    for(var i=0;i<this.length;i++){  

        if(this[i] == n){  

            return i;  

        }  

    }  

    return -1;  

}  

function removeDup(arr,s,e){  

    if(s==e){  

        //分割就剩下一个  

        return [arr[s]]  

    }else if(s==e-1){  

        //为了优化 剩下两个就不用分割啦  

        if(arr[s]==arr[e]){  

            return [arr[s]]  

        }else{  

            return [arr[s],arr[e]];  

        }  

    }  

    //数组平分成两段,  

    var l = Math.floor((s+e)/2);  

    //左边  

    var arrL = removeDup(arr,s,l);  

    //右边  

    var arrR = removeDup(arr,l+1,e);  

    //结果 先把左边的复制进去  

    var result = arrL;  

    //循环 将不重复的数据插入到结果里面  

    for(var i=0;i<arrR.length;i++){  

        if(result.indexOf(arrR[i])== -1 ) result.push(arrR[i])  

    }  

    return result; //返回结果  

}  

var arrDup = removeDup(arr, 0, arr.length-1);  

document.write(arr+'<br/>'+arrDup);  

 

讲解:将重复的数组 切割,拆分到最后只剩下一个数据或或者两个数组,将左边的数据放到结果里面,右边重复的跳过 不重复插入,直到循环完,返回结果就可以

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数组 算法
上一篇:query二级菜单,鼠标经过显示二级分类,大类和小类都有链接
下一篇:使用js实现html锚功能,可以任意定位锚的位置,比锚更加灵活
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站