写在前面这是《学习JavaScript数据结构与算法》的最后一篇博客，也是面试中经常被问到的部分内容：排序与查找。写这篇博??文之前，经常看到排序表头很大，想着“冒泡排序，二级遍历出栈”之类的就完了，后来就不想深究排序相关的问题了。如果您有类似的经历，希望以下内容对您有所帮助。1、进入正题前，准备几个基本函数（1）交换数组函数swap(arr,sourceIndex,targetIndex){lettemp=arr[sourceIndex];arr[sourceIndex]=arr[targetIndex];arr[targetIndex]=temp;}(2)快速生成0~N的数组，点击查看更多生成方法functioncreateArr(length){returnArray.from({length},(_,i)=>i);}(3)Shuffle函数Shuffle函数可以快速对数组进行打乱，常用的用法如切换音乐播放顺序函数shuffle(arr){for(leti=0;iarr[j+1]){//比较相邻元素swap(arr,j,j+1);}}}returnarr;}2.2选择排序选择排序是一种in-位置比较排序算法。核心：先在未排序的序列中找到最小的元素，将其存放在已排序序列的开头，然后继续从剩余未排序的元素中寻找最小的元素，然后将其放在已排序序列的末尾。以此类推，直到所有元素都排好注：第一层遍历找到剩余元素最小值的索引，然后交换当前位置和最小索引值【依次求最小值】代码：functionselectionSort(arr){constlen=arr.length;letminIndex;for(leti=0;iarr[j]){minIndex=j;//求最小值对应的index}}if(minIndex===i)continue;swap(arr,minIndex,i);}returnarr;}2.3插入排序插入排序比较顺序不同于冒泡排序和选择排序。插入排序的比较顺序是当前项向前比较。核心：通过构造有序序列，对于未排序的数据，在已排序的序列中从后往前扫描，找到对应的位置插入注意：从第二项开始，向前比较，以保证前面的序列当前项目有序安排代码：functioninsertionSort(arr){constlen=arr.length;letcurrent,pointer;for(leti=1;i=0&¤tright[0]){ret.push(right.shift());}else{ret.push(left.shift());}}while(left.length){ret.push(left.shift());}while(right.length){ret.push(right.shift());}returnret;}2.5快速排序快速排序可能是最常用的排序算法。它的复杂度为O(nlogn)，其性能通常优于其他O(nlogn)排序算法。和归并排序一样，快速排序也是采用分而治之的方法，将原数组分成更小的数组。遍历过滤掉小于参考点的值代码：functionquickSort(arr,left=0,right=arr.length-1){//左右默认为数组首尾if(leftitem){high=mid-1;}else{returnmid;}}return-1;}4.算法复杂度4.1理解大O符号大O符号用于描述算法的性能和复杂度。在分析算法的时候，我们经常会遇到几类函数(1)O(1)functionincrement(num){return++num;}执行时间与参数无关。因此，上述函数的复杂度为O(1)（常数）（2）O(n)。以顺序查找功能为例，查找一个元素需要遍历整个数组，直到找到该元素。函数执行的总成本取决于数组元素的数量（数组大小），也取决于搜索的值。但函数复杂度取决于最坏情况：如果数组大小为10，则开销为10；如果数组大小为1000，则开销为1000。此函数的时间复杂度为O(n)，其中n是（输入）数组的大小(3)O(n2)以冒泡排序为例，在未优化的情况下，每次排序需要n*执行n次。时间复杂度为O(n2)时间复杂度为O(n)的代码只有一层循环，而O(n2)的代码有两层嵌套循环。如果算法有三层嵌套循环遍历数组，其时间复杂度很可能是O(n3)4.2时间复杂度比较（1）常见数据结构的时间复杂度（2）排序算法的时间复杂度
