简单实现几种排序算法

[lxinr]

冒泡排序

依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位，再对最后一位以外的数组，重复前面的过程，直至全部排序完成

/**
 * @description 冒泡排序
 * @date 2019-04-25
 * @param {*} arr
 * @param {boolean} [reverse=false] 是否倒序排列，即从大到小排序
 */
function bubbleSort(arr, reverse = false) {
  let len = arr.length
  // 确保遍历了每一项
  for(let i = 0; i < len; i++) {
    // 只需要遍历未排序部分
    // 如len = 5，第一次遍历前四项，拿到一个最大值
    // 第二次只需要遍历前三项，拿到仅次于最大值的值，以此类推
    for(let j = 0; j < len - 1 - i; j++) {
      const bool = reverse ? arr[j] < arr[j + 1] : arr[j] > arr[j + 1]
      if (bool) [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
    }
  }
  return arr
}

选择排序

选择排序（Selection Sort）与冒泡排序类似，也是依次对相邻的数进行两两比较。不同之处在于，它不是每比较一次就调换位置，而是一轮比较完毕，找到最大值（或最小值）之后，将其放在正确的位置，其他数的位置不变

function selectionSort(arr) {
  const len = arr.length
  // 确保遍历每一项
  for(let i = 0; i < len; i++) {
    let minIndex = i
    // 从初始最小值之后一项开始判断
    for (let j = i + 1; j < len; j++) {
      // 如果当前项小于最小值
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if(minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  return arr
}

插入排序

插入排序(insertion sort) 方法从数组第二项开始遍历，因假定第一项已经排序，遍历过程中，逐项对比，如果已排序部分的某一项大于对比项，则将当前项向后移一位，再将前一位与对比项比较。直到排序完成，在排序小型数组时，插入排序比选择和冒泡排序性能要好。

function insertionSort(arr) {
  let cloneArr = [...arr]
  let len = cloneArr.length
  for(let i = 1; i < len; i++) {
    let temp = cloneArr[i]
    let j = i
    // 当已排序部分的当前元素大于temp，就将当前元素向后移一位，再将前一位与temp比较
    while(j > 0 && cloneArr[j - 1] > temp) {
      cloneArr[j] = cloneArr[j - 1]
      j--
    }
    // 交换项
    cloneArr[j] = temp
  }
  return cloneArr
}

[lxinr]

掘金 => 六种排序算法的JavaScript实现以及总结