前言最近重（进）捡（门）算法，算法渣。只能记笔记，换取一点安慰。会总结成一个系列。如“递归和回溯”、“深度和广度优先”、“动态规划”、“二分查找”和“贪心”。冒泡排序（BubbleSort）的基本思想给定一个数组，我们将数组中的所有元素倒入池中，这些元素会相互比较并像泡泡一样按照大小的顺序一个接一个地浮出水。冒泡排序实现每一轮，从无序的数组头部开始，比较每两个元素的大小并进行交换，直到本轮最大或最小的元素放在数组尾部，然后不断重复这个过程,直到所有元素对齐。其中，最核心的操作就是元素之间的比较。冒泡排序实例分析给定一个数组[2,1,7,9,5,8]，要求从左到右，从小到大排序。冒泡排序通过从左向右冒泡来解决问题，只需将较大的数字向右移动即可。首先，指针指向第一个数，比较第一个数和第二个数的大小。由于2大于1，因此交换了两对，[1,2,7,9,5,8]。接下来将指针向前移动一步，比较2和7。由于2小于7，所以两者不变，[1,2,7,9,5,8]。7是迄今为止最大的数字。指针继续向前移动，比较7和9，由于7小于9，所以都保持静止，[1,2,7,9,5,8]。现在，9是最大的数字。进一步比较9和5，显然9比5大，交换位置，[1,2,7,5,9,8]。最后比较9和8，9大于8，交换位置，[1,2,7,5,8,9]。第一轮两两比较后，最大的9像冒泡一样到达了数组的末尾。接下来进行第二轮比较，指针重新指向第一个元素，重复上述操作。最后，数组变为：[1,2,5,7,8,9]。在新一轮比较中，判断上一轮比较中是否存在pairwiseexchange。如果没有发生交换，则证明数组实际上已经排序。冒泡排序代码示例//冒泡排序算法constbubbleSort=function(arr){constlen=arr.length//标记每一轮是否发生交换lethasChange=true//如果没有发生交换，则为已经排列好的序列,直接跳出外层遍历for(leti=0;iarr[j+1]){lettemp=arr[j]arr[j]=arr[j+1]arr[j+1]=temphasChange=true}}}}constarr=[2,1,7,9,5,8]bubbleSort(arr)console.log('arr:',arr)冒泡排序算法分析冒泡排序空间复杂度假设数组元素个数为n，因为在整个排序中process中，我们直接交换给定数组中的元素对，所以空间复杂度为O(1)。冒泡排序时间复杂度给定的数组已按顺序排序。在这种情况下，我们只需要进行n-1次比较，成对交换的次数为0，时间复杂度为O(n)。这是最好的情况。给定的数组以相反的顺序排序。这种情况下，我们需要做n(n-1)/2次比较，时间复杂度为O(n2)。这是最坏的情况。给定的数组是杂乱无章的。在这种情况下，平均时间复杂度为O(n2)。可以看出，冒泡排序的时间复杂度是O(n2)。是一种稳定的排序算法。（稳定性是指如果数组中有两个相等的数，排序前后两个相等数的相对位置保持不变。）插入排序的基本思想是将未排序的数不断插入到已排序的部分。插入排序特点冒泡排序中，每一轮排序处理后，对数组后端的数进行排序；对于插入排序，每一轮排序处理后，对数组前端的数进行排序。插入排序实例分析对数组[2,1,7,9,5,8]进行插入排序。插入排序解题思路先把数组分成左右两部分，左边是已经排好序的部分，右边是还没有排好序的部分。一开始左边排好序的部分只有第一个元素2，接下来我们把右边的元素一个一个处理，放到左边。我们先看1。由于1小于2，所以需要在2前面插入1。方法很简单，两两交换位置即可，[1,2,7,9,5,8]。然后，我们需要在左边部分插入7。由于7已经大于2，说明它是当前最大的元素，位置不变，[1,2,7,9,5,8]。同样，9不需要改变它的位置，[1,2,7,9,5,8]。接下来，如何将5插入到合适的位置。先比较5和9，因为5比9小，所以成对交换，[1,2,7,5,9,8]，继续，因为5比7小，所以成对交换，[1,2,5,7,9,8]，最后，由于5大于2，本轮结束。最后一个数是8，由于8小于9，所以交换两对，[1,2,5,7,8,9]，然后比较7和8，发现8大于7，这一轮结束。至此，插入排序就完成了。插入排序代码示例//插入排序constinsertionSort=function(arr){constlen=arr.lengthfor(leti=1;i=0;j--){//current小于j指向的左值，将j指向的左值向右移动一个if(current=hi)return//将数组从中间一分为二letmid=lo+Math.floor((hi-lo)/2)console.log('mid',mid)//分别对左右两半进行递归排序mergeSort(arr,lo,mid)mergeSort(arr,mid+1,hi)//合并排序后的左右两半merge(arr,lo,mid,hi)}constmerge=function(arr,lo,mid,hi){//复制原数组constcopy=[...arr]//定义一个k指针，表示从哪里开始修改原数组，//i指针表示左半部分的起始位置//j指针是右半部分的实际位置letk=loleti=loletj=mid+1while(k<=hi){if(i>mid){arr[k++]=copy[j++]}elseif(j>hi){arr[k++]=copy[i++]}elseif(copy[j]=hi)return//使用分区函数找一个随机参考点constp=partition(arr,lo,hi)//递归对齐引用对左半边和右半边的数字进行排序quickSort(arr,lo,p-1)quickSort(arr,p+1,hi)}//交换数组的位置constswap=function(arr,i,j){lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}//获取随机位置索引constrandomPos=function(lo,hi){returnlo+Math.floor(Math.random()*(hi-lo))}constpartition=function(arr,lo,hi){constpos=randomPos(lo,hi)控制台。log('pos:',pos)swap(arr,pos,hi)leti=loletj=lo//从左到右比较每个数和参考值，如果小于参考值，就放在指针i指向的位置//循环完成后，i指针之前的数都小于参考值while(j
