https://juejin.cn/book/6844733800300150797/section/6844733800367439885

<!-- more -->

基础排序算法

冒泡排序

const bubbleSort = (arr) => {
  let length = arr.length;
  for (let i = 0; i < length; i++) {
    let flag = false;
    for (let j = 0; j < length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        flag = true;
      }
    }
    if (flag === false) return arr;
  }
  return arr;
};
console.log(bubbleSort([4, 5, 2, 8, 1]));

选择排序

const selectSort = (arr) => {
  let length = arr.length;
  let minIndex;
  for (let i = 0; i < length - 1; i++) {
    minIndex = i;
    for (let j = i; j < length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
};
console.log(selectSort([4, 5, 2, 8, 1]));

插入排序

const insertSort = (arr) => {
  let length = arr.length;
  let temp;
  for (let i = 1; i < length; i++) {
    let j = i;
    temp = arr[i];
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
};
console.log(insertSort([4, 5, 2, 8, 1]));

进阶排序算法

归并排序

function mergeSort(arr) {
  const len = arr.length;
  // 处理边界情况
  if (len <= 1) {
    return arr;
  }
  // 计算分割点
  const mid = Math.floor(len / 2);
  // 递归分割左子数组，然后合并为有序数组
  const leftArr = mergeSort(arr.slice(0, mid));
  // 递归分割右子数组，然后合并为有序数组
  const rightArr = mergeSort(arr.slice(mid, len));
  // 合并左右两个有序数组
  arr = mergeArr(leftArr, rightArr);
  // 返回合并后的结果
  return arr;
}

function mergeArr(arr1, arr2) {
  // 初始化两个指针，分别指向 arr1 和 arr2
  let i = 0,
    j = 0;
  // 初始化结果数组
  const res = [];
  // 缓存arr1的长度
  const len1 = arr1.length;
  // 缓存arr2的长度
  const len2 = arr2.length;
  // 合并两个子数组
  while (i < len1 && j < len2) {
    if (arr1[i] < arr2[j]) {
      res.push(arr1[i]);
      i++;
    } else {
      res.push(arr2[j]);
      j++;
    }
  }
  // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
  if (i < len1) {
    return res.concat(arr1.slice(i));
  } else {
    return res.concat(arr2.slice(j));
  }
}

快速排序

const quickSort = (arr) => {
  if (arr.length <= 1) return arr;
  let middleIndex = Math.floor(arr.length / 2);
  // let middleValue = arr[middleIndex]; // 这样写会报内存溢出
  let middleValue = arr.splice(middleIndex, 1)[0]; // 必须要改变原数组
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < middleValue) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([middleValue], quickSort(right));
};
console.log(quickSort([4, 5, 2, 8, 1]));

参考链接

https://juejin.cn/book/6844733800300150797/section/6844733800367439885