排序

一些排序算法的复杂度：
在这里插入图片描述

冒泡排序法

时间复杂度：O(n^2)

相邻的元素进行比较，若存在大小关系就进行交换，如此循环直到数组有序

function BubbleSort(arr){let len=arr.lengthfor(let i=0;i<len;i++){for(let j=0;j<len-1;j++){if(arr[j]>arr[j+1]){let temp=arr[j]arr[j]=arr[j+1]arr[j+1]=temp   //数据交换}}}return arr;
}
console.log(BubbleSort([2,5,3,1,6,4,2]))  //[1, 2, 2, 3, 4, 5, 6]

选择排序法

时间复杂度：O(n^2)

每一趟排序都是从当前无序序列中找出最小数并记录其下标，然后将这个最小数和当前无序序列的第一个数进行交换；如此循环直到数组有序

function SelectSort(arr){let len=arr.lengthfor(let i=0;i<len;i++){var min=arr[i];var k=i; for(let j=i+1;j<len;j++){    //每次循环找出后面的最小值及其下标if(arr[j]<min){k=j;min=arr[j]}}if(k!=i){let temp=arr[k]arr[k]=arr[i]arr[i]=temp}}return arr
}
console.log(SelectSort([2,5,3,1,6,4,2]))  //[1, 2, 2, 3, 4, 5, 6]

插入排序法

时间复杂度：O(n^2)

将数组第一个元素看做已经排序好的，按顺序遍历后面未排序的数据，每遍历到一个，将它和已经排序的数组元素进行比较,将它插入到合适的位置

function InsertSort(arr){let len=arr.length;for(let i=1;i<len;i++){let flag=ilet compare=arr[i]for(let j=i-1;j>=0;j--){if(arr[j]>compare){flag=j;arr[j+1]=arr[j]}}arr[flag]=compare}return arr;
}
console.log(InsertSort([2,5,3,1,6,4,2]))  //[1, 2, 2, 3, 4, 5, 6]

快速排序法

时间复杂度：O(nlogn)

快排是冒泡排序的改进版。
1、从序列中选择一个基准数（一般选择第一个数）。
2、遍历数组，小于基准的放在基准数左边，大于基准的放在右边。
分区结束后，该基准数就处于数组的中间位置，这个称为分区操作。
3、递归，直至数组有序。

function QuickSort(arr){if(arr.length<=1) return arrlet pivot=arr.splice(0,1)[0]  //基准数(每次都要删除数组的第一个元素，将它作为基准数)let left=[],right=[]for(let i=0;i<arr.length;i++){if(arr[i]<pivot) left.push(arr[i])else right.push(arr[i])}return QuickSort(left).concat([pivot],QuickSort(right))
}
console.log(QuickSort([2,5,3,1,6,4,2]))  //[1, 2, 2, 3, 4, 5, 6]
console.log(QuickSort([3,8,6,4])   //[3,4,6,8]   //这种情况时，left会为空，所以递归结束的条件要包含数组长度为0

归并排序法

时间复杂度：O(nlogn)

分而治之的思想，先拆分再合并
1、先将数组拆分，直至拆分出来的子数组长度为1；
2、将有序子数组进行合并。

合并数组：初始化一个数组用来存储合并的数，比较两个已排序的数组第一个元素的大小，并将较小元素删除然后放入合并数组中。

//合并数组函数
function merge(arr1,arr2){let res=[]while(arr1.length>0&&arr2.length>0){if(arr1[0]>arr2[0]){res.push(arr2.shift())}else{res.push(arr1.shift())}}return res.concat(arr1,arr2)
}
//归并排序
function MergeSort(arr){if(arr.length==1) return arrlet mid=Math.floor(arr.length/2)let arr1=arr.slice(0,mid)let arr2=arr.slice(mid)return merge(MergeSort(arr1),MergeSort(arr2))
}
console.log(MergeSort([2,5,3,1,6,4,2]))  //[1, 2, 2, 3, 4, 5, 6]