前端开发必知：五种核心排序算法原理与实现详解

// 1. 冒泡排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const 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]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
};
console.log("bubbleSort:",bubbleSort(arr));
//bubbleSort: [1, 2, 3, 5, 6, 7, 8, 9]

// 2. 选择排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const selectSort = (arr) => {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let maxIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;
      }
    }
    let tmp = arr[i];
    arr[i] = arr[maxIndex];
    arr[maxIndex] = tmp;
  }
  return arr;
};
console.log("selectSort:",selectSort(arr));
//selectSort: [1, 2, 3, 5, 6, 7, 8, 9]

// 3. 插入排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const insertSort = (arr) => {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let current = arr[i];
    let prev = i - 1;
    while (prev >= 0 && current < arr[prev]) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = current;
  }
  return arr;
};

console.log("insertSort:", insertSort(arr));
//insertSort: [1, 2, 3, 5, 6, 7, 8, 9]

// 4. 快速排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

function quickSort(arr){
  if(arr.length <2 ) return arr
  let first = arr[0]
  let left = [], right=[]
  for(let i = 1 ; i <arr.length; i++){
    if(first > arr[i]){
      right.push(arr[i])
    }else{
      left.push(arr[i])
    }
  }
  return [...quickSort(left) , first , ...quickSort(right)]
} 

console.log('quickSort:',quickSort(arr));
//quickSort: [1, 2, 3, 5, 6, 7, 8, 9]

// 5. 归并排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let middle = Math.floor(arr.length / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle, arr.length);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(left.shift());
    }
  }
  // 这也可以采用 while
  if (left.length) {
    result.push(...left);
  }

  if (right.length) {
    result.push(...right);
  }
  return result;
}

console.log("mergeSort:", mergeSort(arr));
//mergeSort: [1, 2, 3, 5, 6, 7, 8, 9]