程序员必备的几种常用排序算法和搜索算法总结搜索算法知识，虽然还有很多高级算法需要了解，但是基础还是要夯实的。本文将以图文形式介绍以下算法知识。希望大家看完：冒泡排序及其优化选择排序插入排序归并排序快速排序顺序搜索*二分查找有所收获。我想每个前端工程师最头疼的就是算法问题，但是算法往往是衡量一个人编程能力的一个非常重要的指标。目前很多主流的框架和库都应用了大量的算法和设计模式。为了让自己的段位更高，只能通过“杀怪”（也就是刷算法）不断升级，成为“最强王者”。应用（如淘宝、微信）都在追求极致的用户体验，时间就是金钱。这就要求工程师只要能用就不要开发程序。我们往往要进行更详细的测试（包括单元测试、性能测试等），以排序为例，对于大规模数据量的排序，我们一定要疯狂吐槽使用冒泡排序，因为性能冒泡排序极差（复杂度为O(n^2)。在实际项目中，我们往往不使用冒泡排序，更多的时候使用快速排序或者希尔排序。排序算法的性能我在上一篇文章，有兴趣的可以参考一下，接下来，我们一起来学习如何实现文章开头的几种常用的排序和查找算法冒泡排序及其优化我们在学习排序算法的时候，最简单的要掌握的是冒泡排序，因为实现起来很简单，但是从运行性能上来说，是最差的。冒泡排序的思想是比较任意两个相邻的项。如果以前的比后者大，它们将被交换。为了更方便展示冒泡排序和性能测试的过程，笔者先写了几个工具和方法，分别是动态生成指定数的随机数组，以及生成元素位置序列的方法。代码如下：//生成一个指定数的随机数组constgenerateArr=(num=10)=>{letarr=[]for(leti=0;i{letpos=[]for(leti=0;iarr[j+1]){//replacement[arr[j],arr[j+1]]=[arr[j+1],arr[j]]}}}returnarr}接下来我们来测试一下，我们使用generateArr方法生成一个60个数组项的数组，并动态生成元素坐标//Generatecoordinatesconstpos=generateArrPosX(60)//生成60个数组项的数组constarr=generateArr(60)css部分这里就不介绍了，大家可以自己实现.然后我们就可以测试我们上面写的冒泡排序了。当我们点击排序时，结果如下：可以看到数组已经排好序了，我们可以用console.time来衡量代码执行的时间，上面的“乞丐版”冒泡排序耗时0.2890625毫秒。深入分析代码可知，两层for循环排序导致了很多冗余排序。如果我们在内循环中减去外循环已经运行的轮数，就可以避免内循环中不必要的比较，所以我们的代码优化如下：//冒泡排序优化版bubbleSort(arr=[]){letlen=arr.length//针对(leti=0;iarr[j+1]){//replacement[arr[j],arr[j+1]]=[arr[j+1],arr[j]]}}}returnarr}优化冒泡排序耗时：0.279052734375ms,比以前稍微好一点，但仍然不是推荐的排序算法。选择排序选择排序的思想是在数据结构中找到最小值放在第一位，然后找到第二个最小值放在第二位，以此类推。我们还是按照之前的模式生成一个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。归并排序归并排序算法的性能优于以上三种，可以在实际项目中投入使用，但实现方法相对复杂。归并排序是一种分而治之的算法。它的思想是将原数组分成更小的数组，直到每个小数组只有一个元素，然后将小数组合并成更大的数组，最后成为一个排序好的大数组。大批为了实现这个方法，我们需要准备一个合并函数和一个递归函数，具体实现代码如下：//mergesortmergeSortRec(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))}//合并方法合并（左，右）{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}顺序搜索搜索算法也是我们的算法之一经常用One，比如我们需要找一个用户或者一段数据，不管是在前端还是在后端，我们都会用到搜索算法。先介绍一下最简单效率最低的顺序搜索。主要思想是将每个数据结构中的元素与我们要查询的元素进行比较，然后返回指定元素的索引。顺序查找之所以效率低下，是因为每次都从数组头部开始查询，直到找到要查找的值，整体查询不够灵活和动态。顺序搜索代码实现如下：sequentialSearch(arr,item){for(leti=0;iitem){max=mid-1}else{returnmid}}return-1}其实搜索算法有很多，我在之前的文章中已经介绍过了，有兴趣的可以学习参考。
