程序员必备的几种常用排序算法和搜索算法总结搜索算法知识，虽然还有很多高级算法需要了解，但是基础还是要夯实的。本文将以图文形式介绍以下算法知识。希望大家看完后有所收获：冒泡排序和Itoptimizesselectionsortinsertionsortmergesortquicksortordersearchbinarysearchtext我想对于每个前端工程师来说，最头疼的就是算法问题，但是算法往往是一个衡量一个人编程能力的非常重要的指标。目前，很多主流的框架和库都应用了大量的算法和设计模式。为了让自己的段位更高，只能不断“杀怪”（也就是刷算法），升级成为“最强王者”。其实前端开发这么多年，越来越倾向于精细化开发。许多超级应用（如淘宝、微信）都在追求极致的用户体验。时间就是金钱。这就要求工程师只要能用就不要开发程序。我们经常需要进行更详细的测试（包括单元测试、性能测试等）。以排序为例。对于大规模数据量的排序，使用冒泡排序肯定要被疯狂吐槽，因为冒泡排序性能极差（复杂度为O(n^2)），在实际项目中，我们往往不用冒泡排序，里面有详细的介绍，接下来我们就来学习如何实现文章开头的几种常见排序和排序搜索算法。1.冒泡排序及其优化我们在学习排序算法的时候，最容易掌握的就是冒泡排序，因为实现起来很简单，但是从运行性能来看，是性能最差的一种。冒泡排序的实现思路是比较任意两个相邻的项，如果前者大于后者，他们会互换，为了更方便的展示冒泡排序的过程和性能测试，笔者先写了几个工具方法，就是动态生成一个指定数的随机数组，以及一个方法来生成一个元素位置序列，代码如下：//生成一个指定数的随机数组constgenerateArr=(num=10)=>{letarr=[]for(leti=0;我<数;i++){letitem=Math.floor(Math.random()*(num+1))arr.push(item)}returnarr}//生成指定数元素x轴坐标constgenerateArrPosX=(n=10,w=6,m=6)=>{letpos=[]for(leti=0;iarr[j+1]){//排列[arr[j],arr[j+1]]=[arr[j+1],arr[j]]}}}returnarr}接下来我们测试一下，我们使用generateArr方法生成一个包含60个数组项的数组，动态生成元素坐标//生成坐标constpos=generateArrPosX(60)//生成一个arrayof60itemsconstarr=generateArr(60)执行代码后，会生成如下图的随机节点结构：css部分这里不做介绍，大家可以自己实现。接下来，我们可以测试我们上面写的冒泡排序。当我们点击排序时，结果如下：可以看到数组已经按顺序排列好，我们可以使用console.time来衡量代码执行的耗时。上面的“乞丐版”冒泡排序耗时0.2890625ms。我们深入分析一下代码就知道，两层for循环排序导致了很多冗余，如果将内循环减去外循环已经运行的轮数，就可以避免内循环不必要的比较循环，所以我们的代码优化如下：//冒泡排序优化版bubbleSort(arr=[]){letlen=arr.length//optimizedfor(leti=0;iarr[j+1]){//排列[arr[j],arr[j+1]]=[arr[j+1],arr[j]]}}}returnarr}优化后的冒泡排序耗时：0.279052734375ms，比之前稍微好一些，但仍然不是推荐的排序算法。2.选择排序选择排序的思想是在数据结构中找到最小值放在第一位，然后找到第二小的值放在第二位，以此类推。我们还是按照之前的模式生成一个60项的数组，如下：选择排序代码如下：selectionSort(arr){letlen=arr.length,indexMinfor(leti=0;iarr[j]){indexMin=j}}if(i!==indexMin){[arr[i],arr[indexMin]]=[arr[indexMin],arr[i]]}}returnarr}点击排序时，结果如下：说明代码运行正常，可以实现排序。控制台耗时为：0.13720703125ms，明显优于冒泡排序性能。排序，然后和第二项比较，确定第二项的位置，然后用同样的方法确定第三项的位置，以此类推，最后将整个数组从小到大排序。代码如下：insertionSort(arr){letlen=arr.length,j,temp;for(leti=1;i0&&arr[j-1]>temp){arr[j]=arr[j-1]j--}arr[j]=temp;}}执行结果如下：控制台打印时间为：0.09912109375ms。4.归并排序归并排序算法性能比上面三种都不错，可以在实际项目中投入使用，但是实现方法比较复杂。合并排序是一种分而治之的算法。思路是将原数组分成更小的数组，直到每个小数组只有一个元素，然后再将小数组合并成更大的数组，最后成为排序好的大数组。实现过程如下图所示：为了实现这个方法，我们需要准备一个合并函数和一个递归函数。具体实现如下：//合并排序mergeSortRec(arr){letlen=arr.lengthif(len===1){returnarr}letmid=Math.floor(len/2),left=arr.slice(0,mid),right=arr.slice(mid,len)returnmerge(mergeSortRec(left),mergeSortRec(right))}//合并方法merge(left,right){letresult=[]l=0,r=0;while(l1){index=partition(arr,left,right)if(leftpart){j--}if(i<=j){//排列[arr[i],arr[j]]=[arr[j],arr[i]]i++j--}}returni}7.顺序搜索算法也是我们经常用到的算法之一，比如我们需要找一个用户或者一段数据，无论是在前端还是在后端，我们都会用到搜索算法。先介绍一下最简单效率最低的顺序搜索。主要思想是将每个数据结构中的元素与我们要查询的元素进行比较，然后返回指定元素的索引。顺序查找之所以效率低下，是因为每次都从数组头部开始查询，直到找到要查找的值，整体查询不够灵活和动态。顺序搜索代码实现如下：sequentialSearch(arr,item){for(leti=0;iitem){max=mid-1}else{returnmid}}return-1}其实搜索算法有很多种，作者有详细介绍js基本搜索算法的实现和170万条数据下的性能测试。参考：学习JavaScript数据结构和算法
