zhangdizhangdi

排序算法

冒泡

O(n2) O(1)

相邻元素进行比较，如果前一个元素值大于后一个元素值，则交换，这样一轮下来，将最大的数在最右边冒泡出来。

简单说：把大的往后排

js
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]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
    console.log(`第${i + 1}轮`, arr)
  }
  return arr
}
console.log('🌰', bubbleSort([3, 9, 1, 4, 2]))
执行结果
第1轮 [ 3, 1, 4, 2, 9 ]
第2轮 [ 1, 3, 2, 4, 9 ]
第3轮 [ 1, 2, 3, 4, 9 ]
第4轮 [ 1, 2, 3, 4, 9 ]
🌰 [ 1, 2, 3, 4, 9 ]

选择

O(n2) O(1)

找到数组中最小的值，选中它并放到第一位，接着找到数组中第二小的值，选中它并放到第二位。

简单说：把小的往前排

js
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
    console.log(`第${i + 1}轮`, arr)
  }
  return arr
}
console.log('🌰', selectionSort([3, 9, 1, 4, 2]))
执行结果
第1轮 [ 1, 9, 3, 4, 2 ]
第2轮 [ 1, 2, 3, 4, 9 ]
第3轮 [ 1, 2, 3, 4, 9 ]
第4轮 [ 1, 2, 3, 4, 9 ]
🌰 [ 1, 2, 3, 4, 9 ]

插入

O(n2) O(1)

每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较（它是该插入到第一、第二还是第三的位置呢），以此类推。

简单说：也是把小的往前排

js
function insertionSort(arr) {
  let n = arr.length
  let preIndex, current
  for (let i = 1; i < n; i++) {
    preIndex = i - 1
    current = arr[i]
    //如果不比current小就停止了，prevIndex不会再一直递减到0
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current

    console.log(`第${i}轮`, arr)
  }
  return arr
}
console.log('🌰', insertionSort([3, 9, 1, 4, 2]))
执行结果
第1轮 [ 3, 9, 1, 4, 2 ]
第2轮 [ 1, 3, 9, 4, 2 ]
第3轮 [ 1, 3, 4, 9, 2 ]
第4轮 [ 1, 2, 3, 4, 9 ]
🌰 [ 1, 2, 3, 4, 9 ]

归并

分治 递归 双指针 O(nlogn) O(n)

是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

js
function mergeSort(arr) {
  const rec = arr => {
    //分解
    const len = arr.length
    if (len === 1) {
      return arr
    }
    const mid = Math.floor(len / 2)
    const leftArr = arr.slice(0, mid)
    const rightArr = arr.slice(mid)

    console.log('分解', 'left:', leftArr, 'right:', rightArr)

    const orderLeftArr = rec(leftArr)
    const orderRightArr = rec(rightArr)

    //合并，双指针
    const res = []
    let li = 0 //left index
    let ri = 0 //right index
    while (li < orderLeftArr.length || ri < orderRightArr.length) {
      const lv = orderLeftArr[li] //left number
      const rv = orderRightArr[ri] //right number
      if ((lv && rv && lv < rv) || (lv && !rv)) {
        res.push(lv)
        li++
      } else if ((lv && rv && lv > rv) || (!lv && rv)) {
        res.push(rv)
        ri++
      } else {
        res.push(lv)
        res.push(rv)
        li++
        ri++
      }
    }
    console.log('🈴️ 合并', res)
    return res
  }

  return rec(arr)
}
console.log('🌰', mergeSort([3, 9, 1, 2, 4, 70, 34, 56]))
执行结果
分解 left: [ 3, 9, 1, 2 ] right: [ 4, 70, 34, 56 ]
分解 left: [ 3, 9 ] right: [ 1, 2 ]
分解 left: [ 3 ] right: [ 9 ]
🈴️ 合并 [ 3, 9 ]
分解 left: [ 1 ] right: [ 2 ]
🈴️ 合并 [ 1, 2 ]
🈴️ 合并 [ 1, 2, 3, 9 ]
分解 left: [ 4, 70 ] right: [ 34, 56 ]
分解 left: [ 4 ] right: [ 70 ]
🈴️ 合并 [ 4, 70 ]
分解 left: [ 34 ] right: [ 56 ]
🈴️ 合并 [ 34, 56 ]
🈴️ 合并 [ 4, 34, 56, 70 ]
🈴️ 合并 [
  1,  2,  3,  4,
  9, 34, 56, 70
]
🌰 [
  1,  2,  3,  4,
  9, 34, 56, 70
]

快速

分治 递归 O(nlogn) O(nlogn)

从数组中任意选择一个基准，所有比基准小的元素放在基准前面，比基准大的元素放在基准后面，递归的对基准前后的子数组再进行划分。

js
function quickSort(array) {
  const rec = arr => {
    const len = arr.length
    //!!!leftArr或rightArr可能为空
    if (len <= 1) {
      return arr
    }
    const mid = arr[0]
    const leftArr = []
    const rightArr = []

    for (let i = 1; i < len; i++) {
      const val = arr[i]
      if (val < mid) {
        leftArr.push(val)
      } else {
        rightArr.push(val)
      }
    }
    console.log(`基准: ${mid} 分解`, 'left:', leftArr, 'right:', rightArr)

    const res = [...rec(leftArr), mid, ...rec(rightArr)]
    console.log(`基准: ${mid} 合并`, res)

    return res
  }

  return rec(array)
}
console.log('🌰', quickSort([3, 9, 1, 2, 4, 70, 34, 56]))
执行结果
基准: 3 分解 left: [ 1, 2 ] right: [ 9, 4, 70, 34, 56 ]
基准: 1 分解 left: [] right: [ 2 ]
基准: 1 合并 [ 1, 2 ]
基准: 9 分解 left: [ 4 ] right: [ 70, 34, 56 ]
基准: 70 分解 left: [ 34, 56 ] right: []
基准: 34 分解 left: [] right: [ 56 ]
基准: 34 合并 [ 34, 56 ]
基准: 70 合并 [ 34, 56, 70 ]
基准: 9 合并 [ 4, 9, 34, 56, 70 ]
基准: 3 合并 [
  1,  2,  3,  4,
  9, 34, 56, 70
]
🌰 [
  1,  2,  3,  4,
  9, 34, 56, 70
]

堆

最大堆可以得到一个升序的数组，最小堆可以得到一个降序的数组

用最大堆排序步骤：

  1. 用数组创建一个最大堆
  2. 将堆顶与堆尾（堆最后一个值）交换，将堆.legnth -1
  3. 将剩下的元素不断重复 前 2 步，直到堆大小为 1
js
function heapSort(nums) {
  let heapSize = nums.length
  const len = nums.length
  buildMaxHeap(heapSize)

  console.log('init maxHeap', [...nums])

  while (heapSize > 1) {
    swap(nums, 0, --heapSize)
    maxHeapify(0, heapSize)

    console.log('', heapSize, [...nums])
  }
  return nums

  // 自下而上构建一颗大顶堆
  function buildMaxHeap(heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(i, heapSize)
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(i, heapSize) {
    let l = i * 2 + 1
    let r = i * 2 + 2
    let largest = i
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r
    }
    if (largest !== i) {
      swap(nums, i, largest)
      maxHeapify(largest, heapSize)
    }
  }
  //交换
  function swap(arr, i, j) {
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

console.log('🌰', heapSort([0, 1, 2, 2, 3, 7, 6, 1]))
执行结果
init maxHeap [
  7, 3, 6, 2,
  1, 2, 0, 1
]
 7 [
  6, 3, 2, 2,
  1, 1, 0, 7
]
 6 [
  3, 2, 2, 0,
  1, 1, 6, 7
]
 5 [
  2, 1, 2, 0,
  1, 3, 6, 7
]
 4 [
  2, 1, 1, 0,
  2, 3, 6, 7
]
 3 [
  1, 0, 1, 2,
  2, 3, 6, 7
]
 2 [
  1, 0, 1, 2,
  2, 3, 6, 7
]
 1 [
  0, 1, 1, 2,
  2, 3, 6, 7
]
🌰 [
  0, 1, 1, 2,
  2, 3, 6, 7
]

希尔（插入的改进版）【todo⌛️】

计数【todo⌛️】

桶【todo⌛️】

基数【todo⌛️】