冒泡排序

function bubbleSort (array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[j - 1]) {
        [array[j], array[j - 1]] = [array[j - 1], array[j]]
      }
    }
  }
}

最好情况时间复杂度：O(n) 最坏情况时间复杂度：O(n^2) 平均时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳定

选择排序

function selectionSort (array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    let minIndex = i
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[minIndex]) minIndex = j
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]]
  }
}

最好情况时间复杂度：O(n^2) 最坏情况时间复杂度：O(n^2) 平均时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：不稳定

插入排序

function insertionSort (array) {
  const length = array.length
  for (let i = 1; i < length; i++) {
    const insertValue = array[i]
    // 注：此处可用二分查找
    let j = i - 1
    for (; j >=0; j--) {
      if (array[j] > insertValue) {
        array[j + 1] = array[j]
      } else break
    }
    array[j + 1] = insertValue
  }
}

最好情况时间复杂度：O(n) 最坏情况时间复杂度：O(n^2) 平均时间复杂度：O(n^2) 空间复杂度：O(1) 稳定性：稳定

快速排序

每轮快排的本质就是把基准数字放到排序后它应该在的位置例如 [3, 2, 1] 以 3 为基准，一轮排序后为 [2, 1, 3] ，3 已经到了排序后它应该所在的位置

function sort (array, startIndex = 0, endIndex = array.length - 1) {
  if (startIndex >= endIndex) return
  const pivot = array[startIndex]
  let left = startIndex
  let right = endIndex
  while (left < right) {
    while (left < right && array[right] > pivot) right--
    while (left < right && array[left] <= pivot) left++
    if (left < right) {
      [array[left], array[right]] = [array[right], array[left]]
    }
  }
  [array[startIndex], array[left]] = [array[left], array[startIndex]]
  sort(array, startIndex, left - 1)
  sort(array, left + 1, endIndex)
}

function quickSort (array) {
  sort(array)
}

非递归版：

function partition(array, startIndex = 0, endIndex = array.length - 1) {
  if (startIndex >= endIndex) return -1
  const pivot = array[startIndex]
  let left = startIndex
  let right = endIndex
  while (left < right) {
    while (left < right && array[right] > pivot) right--
    while (left < right && array[left] <= pivot) left++
    if (left < right) {
      [array[left], array[right]] = [array[right], array[left]]
    }
  }
  [array[startIndex], array[left]] = [array[left], array[startIndex]]
  return left
}

function quickSort (array) {
  const stack = [[0, array.length - 1]]
  while (stack.length) {
    const pair = stack.pop()
    const pivot = partition(array, pair[0], pair[1])
    if (pivot !== -1) {
      stack.push([pivot + 1, pair[1]])
      stack.push([pair[0], pivot - 1])
    }
  }
}

最好情况时间复杂度：O(nlogn) 最坏情况时间复杂度：O(n^2) 平均时间复杂度：O(nlogn) 最好情况空间复杂度：O(logn) 平均空间复杂度：O(n) 稳定性：不稳定

堆排序

二叉堆的概念： #19

// 最小堆下沉操作
function down (array, position, length) {
  const target = array[position]
  let parentIndex = position
  let leftChildIndex = 2 * parentIndex + 1
  while (leftChildIndex < length) {
    const rightChildIndex = leftChildIndex + 1
    if (rightChildIndex < length && array[rightChildIndex] < array[leftChildIndex]) leftChildIndex = rightChildIndex
    if (array[leftChildIndex] >= target) break
    array[parentIndex] = array[leftChildIndex]
    parentIndex = leftChildIndex
    leftChildIndex = 2 * parentIndex + 1
  }
  array[parentIndex] = target
}

function heapSort (array) {
  const length = array.length
  // 构建二叉堆
  for (let i = Math.floor((length - 2) / 2); i >= 0; i--) {
    down(array, i, length)
  }
  // 将二叉堆逐个输出，把删除的元素移动到堆末尾
  for (let i = length - 1; i >= 0; i--) {
    const first = array[0]
    array.push(first)
    if (i !== 0) {
      array[0] = array.splice(i, 1)[0]
      down(array, 0, i)
    } else {
      array.splice(i, 1)
    }
  }
}

最好情况时间复杂度：O(nlogn) 最坏情况时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 空间复杂度：O(1) 稳定性：不稳定

归并排序

重点在于“合并”，用到三个指针， p1, p2 分别指向待合并的两个数组， p 指向合并后的数组，对比 p1, p2 所指的值，把较小的值放入合并的数组，并移动较小值的指针，直到一个数组被全部遍历，将未遍历完的数组后面的元素全部放在合并数组的后面。

function merge (array, start, mid, end) {
  const mergedArray = []
  let p1 = start
  let p2 = mid + 1
  let p = 0
  while (p1 <= mid && p2 <= end) {
    if (array[p1] <= array[p2]) {
      mergedArray[p++] = array[p1++]
    } else {
      mergedArray[p++] = array[p2++]
    }
  }
  while (p1 <= mid) mergedArray[p++] = array[p1++]
  while (p2 <= end) mergedArray[p++] = array[p2++]
  const length = mergedArray.length
  for (let i = 0; i < length; i++) {
    array[i + start] = mergedArray[i]
  }
}

function mergeSort (array, start = 0, end = array.length - 1) {
  if (end > start) {
    const mid = start + Math.floor((end - start) / 2)
    mergeSort(array, start, mid)
    mergeSort(array, mid + 1, end)
    merge(array, start, mid, end)
  }
}

最好情况时间复杂度：O(nlogn) 最坏情况时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 空间复杂度：O(n) 稳定性：稳定

希尔排序

本质上希尔排序是插入排序的改进。上述得到，插入排序最好情况的时间复杂度是 O(n) ，即已经是有序的情况，实际上，数组越是有序，插入排序需要对比的次数就越少。那么，可以对数组先进行一个粗粒度的处理，例如给定一个跨度 x ，把间隔为 x 的元素取出来单独进行插入排序，然后再缩小跨度，直到跨度为 1 ，这样，在某些情况下就可以把时间复杂度降低到 O(n^2) 以下。但是遇到一些极端情况，性能反而会比插入排序差，例如 [2, 1, 5, 3, 7, 6, 9, 8] 这组数字，按照 4 或者 2 的跨度处理，顺序都是不变的，最后跨度为 1 时，做了一遍插入排序，前面分组的操作就是白做了。为此，可以改进跨度增量的算法来弥补此缺陷，参考漫画：什么是希尔排序？

function shellSort (array) {
  const length = array.length
  let d = length
  while (d > 1) {
    d = Math.floor(d / 2)
    for (let i = d; i < length; i += d) {
      const insertValue = array[i]
      let j = i - d
      for (; j >= 0; j -= d) {
        if (array[j] > insertValue) {
          array[j + d] = array[j]
        } else break
      }
      array[j + d] = insertValue
    }
  }
}

平均时间复杂度：O(n^1.3) 空间复杂度：O(1) 稳定性：不稳定

计数排序

计数排序适用于符合以下两种条件的数列：

数列中最大值与最小值的差不是很大
数列都为整数

function countSort (array) {
  const length = array.length
  const min = Math.min(...array)
  // JS 数组不用初始化大小，因此不用求最大值
  const countArray = []
  for (let i = 0; i < length; i++) {
    const diff = array[i] - min
    const value = countArray[diff]
    countArray[diff] = (value || 0) + 1
  }
  const countLength = countArray.length
  let sum = 0
  for (let i = 0; i < countLength; i++) {
    sum = sum + (countArray[i] || 0)
    countArray[i] = sum
  }
  const sortedArray = []
  // 倒序遍历是为了变成稳定排序
  for (let i = length - 1; i >= 0; i--) {
    const diff = array[i] - min
    sortedArray[countArray[diff] - 1] = array[i]
    countArray[diff]--
  }
  return sortedArray
}

最好情况时间复杂度：O(n + m) 最坏情况时间复杂度：O(n + m) 平均时间复杂度：O(n + m) 空间复杂度：O(m) , 如果算上结果数组，是 O(n + m) 稳定性：稳定（不做求和操作的计数为不稳定排序）

以上 m 为数列中最大值与最小值的差

桶排序

适用于数列分布较均匀的整数或小数

function bucketSort (array) {
  const length = array.length
  // 桶的个数设置为等于元素个数
  const buckets = []
  const max = Math.max(...array)
  const min = Math.min(...array)
  const range = (max - min) / (length - 1)
  for (let i = 0; i < length; i++) {
    const index = Math.floor((array[i] - min) / range)
    if (!buckets[index]) buckets[index] = []
    buckets[index].push(array[i])
  }
  // 对每一个桶进行 O(nlogn) 的排序
  let index = 0
  const bucketsLength = buckets.length
  for (let i = 0; i < bucketsLength; i++) {
    if (buckets[i]) {
      buckets[i].sort((a, b) => a - b)
      const bucketLength = buckets[i].length
      for (let j = 0; j < bucketLength; j++) {
        array[index++] = buckets[i][j]
      }
    }
  }
}

时间复杂度：O(n + m + n(logn - logm)) 空间复杂度：O(n + m) 稳定性：稳定（内部的 nlogn 排序是稳定的话）

以上 m 为桶的个数

基数排序

把字符串按位拆分，对每一位进行一次计数排序，可用于较长的数字，例如手机号，或者对于字母，例如单词

function radixSort (array) {
  const length = array.length
  let maxStringLength = 0
  // 找出最大字符串长度
  for (let i = 0; i < length; i++) {
    maxStringLength = Math.max(array[i].toString().length, maxStringLength)
  }
  // 对于每一位做计数排序
  for (let i = maxStringLength - 1; i >= 0; i--) {
    const countArray = []
    const sortedArray = []
    for (let j = 0; j < length; j++) {
      const char = array[j].toString()[i]
      const index = char != null ? char.codePointAt(0) : 0
      countArray[index] = (countArray[index] || 0) + 1
    }
    const countLength = countArray.length
    for (let j = 1; j < countLength; j++) {
      countArray[j] = (countArray[j] || 0) + (countArray[j - 1] || 0)
    }
    for (let j = length - 1; j >= 0; j--) {
      const char = array[j].toString()[i]
      const index = char != null ? char.codePointAt(0) : 0
      sortedArray[countArray[index] - 1] = array[j]
      countArray[index]--
    }
    array = sortedArray
  }
  return array
}

时间复杂度：O(k(n + m)) 空间复杂度：O(n + m) 稳定性：稳定

以上 k 为最长字符长度， m 为计数排序最大值与最小值的差值

总结

排序算法	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
希尔排序	O(n^1.3)	O(n^2)	O(n^1.3)	O(1)	不稳定
计数排序			O(n + m)	O(m)，算上存结果的数组是 O(n + m)	稳定
桶排序			O(n + m + n(logn - logm))	O(n + m)	稳定
基数排序			O(k(n + m))	O(n + m)	稳定

参考

漫画：“排序算法” 大总结

ChuChencheng / note

基本排序算法 #18