html网站地图生成器,引流推广的方法,dede门户网站模版,旅游网站制作方法一文了解排序和搜索算法在前端中的应用⏳序言#x1f9ed;一、文章结构抢先知⌚二、排序和搜索1、定义2、JS中的排序和搜索⏰三、排序算法1、冒泡排序#x1f4a1;#xff08;1#xff09;定义#xff08;2#xff09;实现思路#xff08;3#xff09;图例#xff08;… 一文了解排序和搜索算法在前端中的应用⏳序言一、文章结构抢先知⌚二、排序和搜索1、定义2、JS中的排序和搜索⏰三、排序算法1、冒泡排序1定义2实现思路3图例4代码实现2、选择排序1定义2实现思路3图例4代码实现3、插入排序1定义2实现思路3图例4代码实现4、归并排序1定义2实现思路3图例4代码实现5、快速排序1定义2实现思路3图例4代码实现⏲️四、搜索算法1、顺序搜索1定义2实现思路3代码实现2、二分搜索1定义2实现思路3代码实现⏱️五、leetcode经典题目解析1、leetcode21合并两个有序链表简单2、leetcode374猜数字大小简单六、结束语彩蛋 One More Thing️往期推荐️网站推荐️番外篇⏳序言
前面的文章中讲解了各种数据结构那么今天顺着数据结构与算法这个话题我们来谈谈算法。算法一般分为两种一种是排序算法另一种是搜索算法。
在今天的文章中将概括排序和搜索在 js 中的应用同时讲解常见的5种排序算法分别是冒泡排序、选择排序、插入排序、归并排序和快速排序。以及常见的两种搜索算法顺序搜索和二分搜索。
一起来学习吧~
一、文章结构抢先知
在文章开讲之前我们先用一张思维导图来辅助大家了解文章结构。详情见下图 了解完思维导图后接下来开始进入本文的讲解~
⌚二、排序和搜索
1、定义
排序 所谓排序就是把某个乱序的数组变为升序或降序的数组。搜索 所谓搜索就是找出数组中某个元素的下标。
2、JS中的排序和搜索
JS 中的排序数组的 sort() 方法。JS 中的搜索数组中的 indexOf() 方法。
⏰三、排序算法
1、冒泡排序
1定义
冒泡排序即比较相邻的两个元素。如果第一个比第二个大就左右交换它们两个依次进行n轮。
2实现思路
比较所有相邻元素如果第一个比第二个大则交换它们。一轮下来可以保证最后一个数是最大的。执行n - 1轮就可以完成排序。
3图例
下面用一个视频来演示冒泡排序的全过程。详情见下图 数据结构与算法之冒泡排序4代码实现
/*** description 冒泡排序*/Array.prototype.bubbleSort function(){for(let i 0; i this.length - 1; i){for(let j 0; j this.length - 1 - i; j){if(this[j] this[j 1]){const temp this[j];this[j] this[j 1];this[j 1] temp;}}}
}const arr [5, 4, 3, 2, 1];
arr.bubbleSort();
console.log(arr); //[1, 2, 3, 4, 5]2、选择排序
1定义
选择排序即在要排序的一组数中选出最小的数与第一个位置的数交换然后再剩下的数当中再找最小的数与第二个位置的数交换如此循环到倒数第二个数和最后一个数比较为止。
2实现思路
找到数组中的最小值选中它并将其放在第一位。接着找到第二小的值选中它并将其放置在第二位。以此类推执行n - 1轮。
3图例
下面用一个视频来演示选择排序的全过程。详情见下图 数据结构与算法之选择排序4代码实现
/*** description 选择排序*/Array.prototype.selectSort function(){for(let i 0; i this.length - 1; i){let indexMin i;for(let j i; j this.length; j){if(this[j] this[indexMin]){indexMin j;}}if(indexMin ! i){const temp this[i];this[i] this[indexMin];this[indexMin] temp;}}
}const arr [5, 4, 3, 2, 1];
arr.selectSort();
console.log(arr); //[1, 2, 3, 4, 5]3、插入排序
1定义
插入排序是一种将指定元素与某个有序区域比较并交换位置的排序算法。
2实现思路
从第二个数开始往前比。比它大就往后排。以此类推进行到最后一个数。
3图例
下面用一个视频来演示插入排序的全过程。详情见下图 数据结构与算法之插入排序4代码实现
/*** description 插入排序*/Array.prototype.insertionSort function(){for(let i 1; i this.length; i){const temp this[i];let j i;while(j 0){if(this[j - 1] temp){this[j] this[j - 1];}else{break;}j - 1;}this[j] temp;}
}const arr [6, 2, 3, 4, 5];
arr.insertionSort();
console.log(arr); // [2, 3, 4, 5, 6]4、归并排序
1定义
归并排序的实现是使用了一种分而治之的思想即将一个数组不断地通过两两分组的方式进行比较最后知道所有元素都被分到一组里达到整体有序的目的。
2实现思路
划分问题把序列分成元素个数尽量相等的两半递归求解把两半元素分别排序合并问题把两个有序表合并成一个。
3图例
下面用一个视频来演示归并排序的全过程。详情见下图 数据结构与算法之归并排序4代码实现
/*** description 归并排序*/Array.prototype.mergeSort function(){const rec (arr) {if(arr.length 1){return arr;}const mid Math.floor(arr.length / 2);const left arr.slice(0, mid);const right arr.slice(mid, arr.length);const orderLeft rec(left);const orderRight rec(right);const res [];while(orderLeft.length || orderRight.length){if(orderLeft.length orderRight.length){res.push(orderLeft[0] orderRight[0] ? orderLeft.shift() : orderRight.shift());}else if(orderLeft.length){res.push(orderLeft.shift());}else if(orderRight.length){res.push(orderRight.shift());}}return res;}const res rec(this);res.forEach((n, i) { this[i] n; });return res;
}const arr [5, 4, 3, 2, 1];
// arr.mergeSort();
console.log(arr.mergeSort()); // [1, 2, 3, 4, 5]5、快速排序
1定义
快速排序即通过一趟排序将需要排序的数据分割成独立的两部分其中一部分的所有数据比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
2实现思路
分区从数组中任意选择一个“基准”所有比基准小的元素放在基准前面比基准大的元素放在基准的后面。递归递归的对基准前后的子数组进行分区。
3图例
下面用一个视频来演示快速排序的全过程。详情见下图 数据结构与算法之快速排序4代码实现
/*** description 快速排序*//*** 实现思路* 1.先选一个元素作为基点pivot* 2.将其余元素中所有比pivot小的值放在pivot的左边将所有比pivot大的值放在pivot的右边* 3.然后分别对pivot左边的所有元素和右边的所有元素从步骤1开始依次进行排序直到所有元素完整有序。*/Array.prototype.quickSort function(){const rec (arr) {if(arr.length 1){return arr;}const left [];const right [];const mid arr[0];for(let i 1; i arr.length; i){if(arr[i] mid){left.push(arr[i]);}else{right.push(arr[i]);}}return [...rec(left), mid, ...rec(right)];}const res rec(this);res.forEach((n, i) {this[i] n;});return res;
} const arr [2, 4, 5, 3, 1];
console.log(arr.quickSort()); // [1, 2, 3, 4, 5]⏲️四、搜索算法
1、顺序搜索
1定义
顺序搜索是指将每一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。
2实现思路
遍历数组。找到跟目标值相等的元素就返回它的下标。遍历结束后如果没有搜索到目标值就返回-1。
3代码实现
/*** description 顺序搜素*/Array.prototype.sequentialSearch function(item){for(let i 0; i this.length; i){if(this[i] item){return i;}}return -1;
}const res [1 ,2, 3, 4, 5].sequentialSearch(3);console.log(res); // 22、二分搜索
1定义
二分搜索也称折半搜索它是一种效率较高的搜索方法。但是折半搜索要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。
2实现思路
从数组的中间元素开始如果中间元素正好是目标值则搜索结束。如果目标值大于或小于中间元素则在大于或小于中间元素的那一半数组中搜索。
3代码实现
/*** description 二分搜索*/Array.prototype.binarySearch function(item){let low 0;let high this.length - 1;while(low high){const mid Math.floor((low high) / 2);const element this[mid];if(element item){low mid 1;}else if(element item){high mid - 1;}else{return mid;}}return -1;
}const res [1, 2, 3, 4, 5].binarySearch(1);
console.log(res); // 0⏱️五、leetcode经典题目解析
1、leetcode21合并两个有序链表简单
1题意
附上题目链接leetcode21合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入输出示例
输入: l1 [1,2,4], l2 [1,3,4]输出: [1,1,2,3,4,4]
2解题思路
与归并排序中的合并两个有序数组相似。将数组替换成链表就能解决此 题。
3解题步骤
新建一个新链表作为返回结果。用指针遍历两个有序链表并比较两个链表的当前节点较小者先接入新链表并将指针后移一步。链表遍历结束返回新链表。
4代码实现
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} l1* param {ListNode} l2* return {ListNode}*/var mergeTwoLists function(l1, l2) {const res new ListNode(0);let p res;let p1 l1;let p2 l2;while(p1 p2){if(p1.val p2.val){p.next p1;p1 p1.next;}else{p.next p2;p2 p2.next;}p p.next;}if(p1){p.next p1;}if(p2){p.next p2;}return res.next;
};2、leetcode374猜数字大小简单
1题意
猜数字游戏的规则如下
每轮游戏我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了我会告诉你你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果返回值一共有 3 种可能的情况-11 或 0
-1我选出的数字比你猜的数字小 pick num
1我选出的数字比你猜的数字大 pick num
0我选出的数字和你猜的数字一样。恭喜你猜对了pick num
返回我选出的数字。
输入输出示例
输入: n 10, pick 6输出: 6
2解题思路
二分搜索。调用guess函数来判断中间元素是否是目标值。
3解题步骤
从数组的中间元素开始如果中间元素正好是目标值则搜索过程结束。如果目标值大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找。
4代码实现
/** * Forward declaration of guess API.* param {number} num your guess* return -1 if num is lower than the guess number* 1 if num is higher than the guess number* otherwise return 0* var guess function(num) {}*//*** param {number} n* return {number}*/var guessNumber function(n) {let low 1;let high n;while(low high){const mid Math.floor((low high) / 2);const res guess(mid);if(res 0){return mid;}else if(res 1){low mid 1;}else if(res -1){high mid - 1;}}
};六、结束语
算法在前端中的应用还是蛮广泛的比如 js 中的 sort() 和 indexOf() 是基于排序和搜索算法来实现的。同时算法在也是前端面试中的一大必考点对于不会算法的开发者来说无形之中与别人的核心竞争力就会被削减了一大半。
本文主要讲解了一些常见的排序和搜索的基础实现后续大家还可以继续深挖一些其他场景举一反三慢慢的理解就会越来越深入了~
到这里排序和搜索算法的讲解就结束啦希望对大家有帮助~
如文章有误或有不理解的地方欢迎小伙伴们评论区留言撒
彩蛋 One More Thing
️往期推荐
栈栈在前端中的应用顺便再了解下深拷贝和浅拷贝
队列详解队列在前端的应用深剖JS中的事件循环Eventloop再了解微任务和宏任务
链表详解链表在前端的应用顺便再弄懂原型和原型链
字典和集合ES6的Set和Map你都知道吗一文了解集合和字典在前端中的应用
树一文了解树在前端中的应用掌握数据结构中树的生命线
图太平洋大西洋水流问题如何解决一文了解图在前端中的应用
堆最小堆最大堆了解吗一文了解堆在前端中的应用
动态规则和分而治之算法一文了解分而治之和动态规则算法在前端中的应用
贪心算法和回溯算法一文了解贪心算法和回溯算法在前端中的应用
️网站推荐
文章重的可视化动图用到的是 visualgo 网站进行录屏该网站几乎涵盖了所有数据结构和算法的实现包括但不限于排序、位掩码、哈希表、二叉堆和循环查找等等动图的功能。戳此链接可直接进入网站体验可视化~ ️番外篇 关注公众号星期一研究室第一时间关注学习干货更多精选专栏待你解锁~如果这篇文章对你有用记得留个脚印jio再走哦~以上就是本文的全部内容我们下期见
