排序算法

一、冒泡排序

思路：遍历数组，比较相邻的元素，如果比后者大（升序），就交换位置，进行n-1轮

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

过程：
第一趟交换
[8, 4, 2, 5, 2] - [4, 8, 2, 5, 2] - [4, 2, 8, 5, 2] - [4, 2, 5, 8, 2] - [4, 2, 5, 2, 8]
第二趟交换
[4, 2, 5, 2, 8] - [2, 4, 5, 2, 8] - [2, 4, 2, 5, 8]
第三趟交换
[2, 4, 2, 5, 8] - [2, 2, 4, 5, 8]

改进：
思路：当一次遍历前后数组不产生变化时，说明该数组已经有序，结束排序

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

二、选择排序

思路： 找到最小值，放在第一位，然后找到第二小的值，放在第二位，以此类推，执行n-1轮

  function selecttionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
      let min = i
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[min] > arr[j]) min = j
      }
      if (min != i) {
        [arr[min], arr[i]] = [arr[i], arr[min]]
      }
    }
    return arr
  }
  console.log(selecttionSort([3, 2, 5, 1, 4]))

过程：
[3, 2, 5, 1, 4] - [1, 2, 5, 3, 4] - [1, 2, 5, 3, 4] - [1, 2, 3, 5, 4] - [1, 2, 3, 4, 5]

三、插入排序

思路：从数组下标1开始每增1项排序一次，越往后遍历次数越多

  function insertSort(arr) {
    //从数组的第二位开始往左比较，所以i=1
    for (let i = 1; i < arr.length; i++) {
      let target = i; //这个是当前要插入的数，第一次循环默认位第二个数
      for (let j = i - 1; j >= 0; j--) {
        //将target与左边排序好的数比较，如果比较小，则与被比较的数交换位置
        if (arr[target] < arr[j]) {
          const tem = arr[target]
          arr[target] = arr[j]
          arr[j] = tem
        }else{
          //如果前面没有比target小的数，退出循环
          break;
        }
        target = j
      }
    }
    return arr
  }
  let arr = [3, 2, 5, 1, 4]
  console.log(arr)
  console.log(insertSort(arr))

过程：
index = 1: [3, 2, 5, 1, 4] - [2, 3, 5 ,1, 4]
index = 2: [2, 3, 5, 1, 4]
index = 3: [2, 3, 5 ,1, 4] - [2, 3, 1, 5, 4] - [2, 1, 3, 5, 4] - [1, 2, 3, 5, 4]
index = 4: [1, 2, 3, 5, 4] - [1, 2, 3, 4 ,5]

四、归并排序

思路：将无序的数组 拆成N部分进行有序处理，然后合并。
代码参考https://juejin.cn/post/6911517734152962056

  const mergeSort = (arr) => {
    if (arr.length < 2) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2); //获取数组中间下标，将数组分为左右两个数组
    const left = arr.slice(0, mid); //左边数组
    const right = arr.slice(mid, arr.length); //右边数组
    //调用递归将左右两边的数组继续拆分，直到数组长度小于2
    const orderLeft = mergeSort(left); //有序的左边数组，最后return出来的长度为1
    const orderRight = mergeSort(right); //有序的右边数组
    const res = [];
    //当左边或者右边数组有值的情况下
    while (orderLeft.length || orderRight.length) {
      //当左边数组和右边数组都有值的情况下，比较左右两边数组的第一个数，将较小的数推入res中
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
        );
      }
      //如果右边数组值为空，左边不为空，将左边的数全部推入res
      else if (orderLeft.length) {
        res.push(orderLeft.shift()); //删除并返回数组的第一个元素
      } else if (orderRight.length) {
        res.push(orderRight.shift());
      }
    }
    //返回合并后的有序数组作为递归的结果
    return res;
  };
  console.log(mergeSort([9,8,7,6,5,4,3]))

五、快速排序

思路：也是分治思想。找一个数为基准，比它小的放左边，比它大的放右边，然后递归。

  const quickSort = (function a(arr) {
    if (arr.length < 2) return arr
    const mid = arr[0]  //数组的第一位为基准
    const left = []     //比基准小的数组
    const right = []    //比基准大的数组
    //从数组的第二位开始循环与基准进行比较
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < mid) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    //返回值为左边数组+基准元素+右边数组
    return [...a(left), mid, ...a(right)]
  })
  console.log(quickSort([9, 8, 7, 6, 5, 4, 3]))