[前端算法]排序算法

在js中一般用到sort方法

arr.sort((a,b)=>{return a-b
})

基础排序

冒泡排序

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);}

选择排序

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);}

插入排序

插入排序的核心,找到元素在它前面的那个序列中的正确位置

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);}

进阶排序算法

分治思想

分解子问题
求解子问题
合并子问题的解

归并排序

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;}