攻城狮——学习常用排序算法1.冒泡排序优点：所有排序中最简单，容易理解；缺点：时间复杂度O(n^2)，平均来说，是最差的排序方法；因为默认情况下，对于已排序的部分，本次排序还是会进行比较（当然可以改进优化）算法步骤：比较的相邻元素，如果第一个大于第二个，则将两者交换。对每一对相邻的元素做同样的事情，从开始的第一对到最后的最后一对，这样最大的数字放在后面。对除最后一个元素之外的所有元素重复上述步骤。对每个元素继续重复上述步骤，直到排序完成。原理分析：通过比较两个相邻的item（从小到大排序），如果第一个比第二个大，交换位置，元素item向上移动到正确的顺序，就像气泡上升到表面一样，因此这个名字冒泡。constbubbleSort=(arr)=>{constlength=arr.length;for(leti=0;iarr[j+1]){让交换=arr[j];arr[j]=arr[j+1];arr[j+1]=交换；}}}}改进优化：默认情况下，上面的代码在第一轮之后仍然会和所有元素进行循环比较，但实际上上一次循环已经对元素进行了正确的排序，所以可以从innerloop已经循环的轮数，以避免不必要的比较constbubbleSort=(arr)=>{constlength=arr.length;for(leti=0;iarr[j+1]){让交换=arr[j];arr[j]=arr[j+1];arr[j+1]=交换；}}}}二、选择排序的原则：比较原始地址，在数据结构中找到最小值放在第一位，然后在其余的中找到第二小的值放在第二位地点等；代码实现：functionselectionSort(arr){varlength=arr.length;变量最小索引；对于(vari=0;i=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];preIndex--;}arr[preIndex+1]=当前；}returnarr;}示意图4.归并排序原理：归并是一种分而治之的算法，即将原数组分成更小的数组，直到每个小数组只有一个位置，然后将小数组合并成更大的数组，每次合并时都排序，直到最后只有一个排序好的大数组。代码实现（递归）：functionmergeSort(arr){//使用自上而下的递归方法拆分数组varlen=arr.length;如果（len<2）{返回arr;}varmiddle=Math.floor(len/2),left=arr.slice(0,middle),right=arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}//合并数组并排序functionmerge(left,right){varresult=[];while(left.length&&right.length){if(left[0]<=right[0]){结果。推（左移（））；}其他{结果。推（右移（））；}}while(left.length)结果。推（左移（））；while(right.length)结果。推（右移（））；returnresult;}示意图5.快速排序原理：快速排序采用分而治之的策略，将一个序列（列表）分成两个子序列（子列表）。排序步骤：首先，从数组中选择中间项作为基数；然后，创建两个指针，左边的指向数组的第一项，右边的指向数组的最后一项；左指针移动直到找到比基数大的元素，右指针移动直到找到比基数小的元素；然后交换它们；重复以上步骤，直到左指针超过右指针；（这个过程会让树比基数小的都在基数的前面，比基数大的都在基数的后面）最后对分好的小数组（值的子数组）重复前面两步小于基数，和大于基数的值）直到数组完全排序。代码实现functionquickSort(arr,left,right){varlen=arr.length,partitionIndex,left=typeofleft!='number'?0:left,right=typeofright!='number'?len-1:对;如果（左<右）{分区索引=分区（arr，左，右）；quickSort(arr,left,partitionIndex-1);quickSort(arr,partitionIndex+1,右);}returnarr;}functionpartition(arr,left,right){//分区操作varpivot=left,//设置基准值（pivot）index=pivot+1;for(vari=index;i<=right;i++){if(arr[i]pivot){--高;}arr[低]=arr[高];while(low
