默认情况下，sort() 会将元素转换为字符串，然后按照 Unicode 编码的顺序进行排序：
const fruits = ['apple', 'banana', 'cherry', 'date'];
fruits.sort();
console.log(fruits); // 输出: ["apple", "banana", "cherry", "date"]
直接使用默认排序对数字进行排序可能会得到不符合预期的结果，因为它会按字符串比较
为了正确排序数字或实现自定义排序规则，可以向 sort() 传递一个比较函数
比较函数接收两个参数（通常称为 a 和 b），并返回一个数值：
- 如果返回值 小于 0：a 会被排在 b 前面
- 如果返回值 等于 0：a 和 b 的相对位置不变
- 如果返回值 大于 0：b 会被排在 a 前面
//升序
arr.sort((a,b)=>{return a-b
})
基础排序
冒泡排序
我们分最好、最坏和平均来看：
- 最好时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
- 最坏时间复杂度： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
- 平均时间复杂度：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可。
function bubbleSort(arr) {let len = arr.length;for (let i = 0; i < len; i++) {for(let j=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){[arr[j],arr[j+1]] = [arr[j+1],arr[j]]}}}console.log(arr);}
//改进版 最好的时间复杂度 O(n)function bubbleSort2(arr) {let len = arr.length;for (let i = 0; i < len; i++) {//增加标志位let flag = false;for(let j=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){flag = true;[arr[j],arr[j+1]] = [arr[j+1],arr[j]]}}//一次交换都没发生,说明数组是有序的if(!flag){break;}}console.log(arr);}
选择排序
选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)。
function selectionSort(arr) {let len = arr.length;for(let i=0;i<len;i++){for(let j=i+1;j<len;j++){if(arr[i]>arr[j]){[arr[i],arr[j]] = [arr[j],arr[i]]}}}console.log(arr);}
插入排序
插入排序的核心,找到元素在它前面的那个序列中的正确位置
正确地定位当前元素在有序序列里的位置、不断扩大有序数组的范围，最终达到完全排序的目的。
-
最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。
-
最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)
-
平均时间复杂度：O(n^2)
function insertionSort(arr) {let len = arr.length;let temp ; //保存当前变量for(let i=1;i<len;i++){temp = arr[i];let j = i;//j来帮助temp找到自己的位置while(j>0 && temp < arr[j-1]){arr[j] = arr[j-1];j--;}arr[j] = temp;}console.log(arr);}
进阶排序算法
分治思想
分解子问题
求解子问题
合并子问题的解
归并排序
归并排序的时间复杂度就是 O(nlog(n))
- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
- 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
function mergeSort(arr) {const len = arr.length;if (len < 2) {return arr;}//计算分割点const middle = Math.floor(len / 2);//分割数组const leftArr = mergeSort(arr.slice(0, middle));const rightArr = mergeSort(arr.slice(middle, len));//合并两个有序数组return merge(leftArr, rightArr);}
//两个有序数组合并function merge(leftArr, rightArr) {let i = 0;let j = 0;//初始化结果数组const res = [];// 检查 leftArr 和 rightArr 是否为 undefinedconst len1 = leftArr? leftArr.length : 0;const len2 = rightArr? rightArr.length : 0;while (i < len1 && j < len2) {if (leftArr[i] < rightArr[j]) {res.push(leftArr[i]);i++;} else {res.push(rightArr[j]);j++;}}//将剩余的数组元素添加到结果数组中while (i < len1) {res.push(leftArr[i]);i++;}while (j < len2) {res.push(rightArr[j]);j++;}return res;}
快速排序
快速排序在基本思想上和归并排序是一致的，仍然坚持“分而治之”的原则不动摇。区别在于，快速排序并不会把真的数组分割开来再合并到一个新数组中去，而是直接在原有的数组内部进行排序。
快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
//快速排序 o(nlogn)function quickSort(arr,left=0,right=arr.length-1){//定义递归边界,若数组只有一个元素不用排序if(arr.length > 1){//下一次划分左右数组的索引位置const lineIndex = partition(arr,left,right);//对左子数组进行快排if(left<lineIndex-1){quickSort(arr,left,lineIndex-1);}//对右子数组进行快排if(lineIndex<right){quickSort(arr,lineIndex,right);}}return arr;}
--二叉树 02)
