[前端算法]排序算法
在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 是否为 undefined
const 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;
}