北京品牌建设网站公司,网站建设的摊销,广告设计与制作专业培训,西安市建网站找哪家前面我们了解了一些常用的排序算法#xff0c;那么这篇文章我们来看看搜索算法的一些简单实现#xff0c;我们先来介绍一个我们在实际工作中一定用到过的搜索算法——顺序搜索。
1、顺序搜索 其实顺序搜索十分简单#xff0c;我们还是以第一篇文章写好的架子作为基础#… 前面我们了解了一些常用的排序算法那么这篇文章我们来看看搜索算法的一些简单实现我们先来介绍一个我们在实际工作中一定用到过的搜索算法——顺序搜索。
1、顺序搜索 其实顺序搜索十分简单我们还是以第一篇文章写好的架子作为基础在其中加入顺序搜索的方法 //顺序搜索
this.sequentialSearch function(item) {for(var i 0; i array.length; i ) {if(item array[i]) {return i;};};return -1;
}; 我想这个代码没什么好说的。你一定能理解的十分透彻。那么下面我们来看看二分搜索。
2、二分搜索 我们先来做一个简单的游戏。想象一个场景我们在聚会大约有7、8个人这个时候有人提议我们来做个游戏吧。我来想一个1到100的数字你们来猜数字是什么我会依照我想的数字告诉你们猜测的数字是比我脑海中的数字大了还是小了。这就是二分搜索。 与顺序搜索不同的是二分搜索需要在搜索之前对要搜索的数组排序。我们来看下代码 //二分搜索
this.binarySearch function(item) {//先对数组进行快速排序this.quickSort();//low和high是边界指针也就是item是高了还是低了的表示mid是我们数组的中间索引变量element则是对应的mid的元素var low 0,high array.length - 1,mid,element;//如果low小于等于high说明边界范围是合理的。while(low high) {//为mid和element变量赋值。mid Math.floor((low high) / 2);element array[mid];// 如果中间值比我们要找的元素小说明item在中间值的右侧要注意我们的数组时排序过后的数组了。// 所以我们直接让等于0的low的值设置为mid 1,因为itemelement所以item必然在mid 1开始到high的区间范围内。// 下同。if(element item) {low mid 1;} else if(element item) {high mid - 1;} else {return mid;};};return -1;
}; 其实二分搜索也并不难看代码和注释就一定可以看懂的。感觉这篇内容实在是不太多所以我决定再加入一些其他的内容吧。
3、去重 想必大家在面试中被问到过最多的问题就是排序和去重了吧。其实这个东西真的算是老生常谈了但是却又有它存在的必要其实说到底去重更重要的是思想而不是实现就跟前面我们学过的那些数据结构和算法一样。 下面我们就介绍一下去重的一些实现方法吧。 1set方法 set是ES6新增的一种数据结构——集合我在前面的有关集合的章节中也介绍过这种数据结构集合是一种不允许重复的数据存在的数据结构我们刚好可以利用这种特性来为数组去重。如果你还不了解set数据结构可以去这里或者这里查看。 this.uniqueSetWay function () {//array.form方法从类似数组或可迭代对象中创建一个新的数组实例var set new Set(array);return Array.from(set);
};//测试方法
var repeatArray new ArrayList();
repeatArray.insert(1);
repeatArray.insert(1);
repeatArray.insert(3);
repeatArray.insert(3);
repeatArray.insert(5);
repeatArray.insert(7);
repeatArray.insert(7);
repeatArray.insert(9);
repeatArray.insert(9);
repeatArray.insert(8);
console.log(repeatArray.uniqueSetWay()) 要注意的是我们这里仍旧使用了第一章所构建的数组类。 2双循环 //双循环
this.uniqueDoubleCycle function () {var newArr [];var len array.length;var isRepeat;for(var i0; ilen; i ) { //第一次循环isRepeat false;for(var ji 1; jlen; j ) { //第二次循环if(array[i] array[j]){isRepeat true;break;}}if(!isRepeat){newArr.push(array[i]);}}return newArr;
}; 这种方法使用了双重循环设置一个标记位确定我们加入新数组的元素是否是重复的代码很好理解但是这是效率最低的实现方式。 3排序辅助去重 //利用排序算法来辅助判断
this.sortUnique function () {var newArr []; this.quickSort();//将原数组中的第一项放入新数组var newArr [array[0]];// 我们来循环比较for(var i 1; i array.length; i ){//如果新数组中的最后一项与array[i]不想等那么我们就把它加入新数组。if(array[i] ! newArr[newArr.length - 1]){newArr.push(array[i]);}} return newArr;
}; 我们就简单的介绍这三种去重方法其实有关于去重的实现有很多种如果大家想要继续学习有关去重的一些内容我这里给大家贴上几篇不错的文章。这里就不再多说。 1、【 js 算法 】这么全的数组去重你怕不怕 2、也谈JavaScript数组去重 3、js数组去重 当然有关数组去重的文章远不止这些只是个人觉得这些内容还不错。本文中的代码也是借鉴于此。那么本文到这里也就差不多结束了下面会和大家一起学习一下算法模式递归、动态规划等。 最后由于本人水平有限能力与大神仍相差甚远若有错误或不明之处还望大家不吝赐教指正。非常感谢
更多专业前端知识请上
【猿2048】www.mk2048.com
