js三大排序算法

一、冒泡排序

冒泡排序思想：让数组中的当前项和后一项进行比较，如果当前项比后一项大的话则两项交换位置，让大的靠后即可。

function buddle(arr) {
  const newArr = [...arr];
  let temp = null
  for (let i = 0; i < newArr.length - 1; i++) {
    for (let j = 0; j < newArr.length - 1 - i; j++) {
      temp = newArr[j]
      if (newArr[j] > newArr[j + 1]) {
        newArr[j] = newArr[j + 1]
        newArr[j + 1] = temp
      }
    }
  }
  return newArr;
}
let arr = [2, 58, 43, 65, 22, 44, 12, 4]
console.log(buddle(arr)) //[2, 4, 12, 22, 43, 44, 58, 65]

1. 基于原数组arr浅克隆复制出一个新数组newArr，目的是为了不修改原数组。
2. 外层循环控制比较的次数，newArr有8个元素，两两比较只用7次，所以比较的是length-1次。
3. 里层循环控制每一轮比较的次数，每次循环都会把此次循环中最大的元素放在数组末尾，而已经排序好的元素就不用参与循环，相当于第二轮循环每次都会减少一次，所以第二个for的循环次数需要减去i。

二、插入排序

插入排序思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

function insert(arr) {
  let newArr = [];
  newArr.push(arr[0]);
  for (let i = 1; i < arr.length; i++) {
    let tempA = arr[i];
    for (let j = newArr.length - 1; j >= 0; j--) {
      let tempB = newArr[j];
      if (tempA > tempB) {
        newArr.splice(j + 1, 0, tempA);
        break;
      }
      if (j === 0) {
        newArr.unshift(tempA);
      }
    }
  }
  return newArr;
}
let arr = [2, 58, 43, 65, 22, 44, 12, 4];
console.log(insert(arr)); //[2, 4, 12, 22, 43, 44, 58, 65]

1. 准备一个新数组newArr，用来存储已经排序完成的元素，并将原数组arr中的第一个元素放到newArr中。
2. 从第二项开始依次遍历arr，并获取当前遍历的元素tempA。
3. 遍历newArr，声明tempB表示遍历newArr中的每一项，将tempA和tempB做比较，如果tempA比tempB大的话就把tempA放到tempB的右面。
4. 如果遍历newArr到第一项的话，就表示tempA比tempB所有项都小，直接放在newArr的第一项即可。

三、快速排序

快速排序思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

function quick(arr) {
  if (arr.length <= 1) return arr;
  const newArr = [...arr]
  const middleIndex = Math.floor(newArr.length / 2)
  const middleValue = newArr.splice(middleIndex, 1)[0]
  const leftArr = [],
    rightArr = []
  for (let i = 0; i < newArr.length; i++) {
    newArr[i] > middleValue ? rightArr.push(newArr[i]) : leftArr.push(newArr[i])
  }
  return [...quick(leftArr), middleValue, ...quick(rightArr)]
}
const arr = [2, 58, 43, 65, 22, 44, 12, 4]
console.log(quick(arr)) //[2, 4, 12, 22, 43, 44, 58, 65]

1. 基于原数组arr浅克隆复制出一个新数组newArr，目的是为了不修改原数组。
2. 找到数组的中间项middleValue，在newArr中把它移除。
3. 准备左右两个数组leftArr和rightArr，循环剩下数组中的每一项，比当前项小的放到leftArr，反之放到rightArr。
4. 通过递归的方式让leftArr和rightArr持续这样处理，一直到左右两边都排好序为止（最后让左边+中间+右边拼接成为最后的结果）。
5. 结束递归，退出递归的条件是当前递归数组的length小于等于1的话就不用处理。