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⌛️】