排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	不稳定
插入排序	O(n2)	O(n)	O(n)	O(n)	稳定
希尔排序	O(n log n)	O(n log2 n)	O(n log2 n)	O(1)	不稳定
选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
桶排序
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
基数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
堆排序
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定

冒泡排序

思想

• 冒泡排序只会操作相邻的两个数据。
• 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
• 一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

特点

• 优点：排序算法的基础，简单实用易于理解。
• 缺点：比较次数多，效率较低。

bubbleSort.ts

function bubbleSort<T>(arr: T[]): T[] {
  console.time('冒泡排序耗时')

  if (!Array.isArray(arr)) return arr

  const length: number = arr.length
  if (length <= 1) return arr

  let swapped: boolean = false // 添加标志变量

  for (let i = 0; i < length - 1; i++) {
    swapped = false // 每次外层循环开始前重置标志变量

    for (let j = 0; j < length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // 使用临时变量进行交换
        swapped = true // 发生交换时设置标志变量为 true
      }
    }

    if (!swapped) break // 如果没有发生交换，说明数组已经排好序，提前结束排序
  }

  console.timeEnd('冒泡排序耗时')
  return arr
}

example

// case1: 普通数组测试
const arr1 = [6, 3, 8, 2, 9, 1]
console.log('排序前:', arr1)
const sortedArr1 = bubbleSort(arr1)
console.log('排序后:', sortedArr1)
// 排序前: [6, 3, 8, 2, 9, 1]
// 冒泡排序耗时: 0.0341796875 ms
// 排序后: [1, 2, 3, 6, 8, 9]

// case2: 包含重复元素的数组测试
const arr2 = [9, 3, 6, 2, 6, 1, 9, 4]
console.log('排序前:', arr2)
const sortedArr2 = bubbleSort(arr2)
console.log('排序后:', sortedArr2)
// 排序前: [9, 3, 6, 2, 6, 1, 9, 4]
// 冒泡排序耗时: 0.020751953125 ms
// 排序后: [1, 2, 3, 4, 6, 6, 9, 9]

// case3: 空数组测试
const arr3 = []
console.log('排序前:', arr3)
const sortedArr3 = bubbleSort(arr3)
console.log('排序后:', sortedArr3)
// 排序前: []
// 排序后: []

// case4: 只有一个元素的数组测试
const arr4 = [7]
console.log('排序前:', arr4)
const sortedArr4 = bubbleSort(arr4)
console.log('排序后:', sortedArr4)
// 排序前: [7]
// 排序后: [7]

// case5: 已经排好序的数组测试
const arr5 = [1, 2, 3, 4, 5]
console.log('排序前:', arr5)
const sortedArr5 = bubbleSort(arr5)
console.log('排序后:', sortedArr5)
// 排序前: [1, 2, 3, 4, 5]
// 冒泡排序耗时: 0.0048828125 ms
// 排序后: [1, 2, 3, 4, 5]

// case6: 随机生成数组测试
const arr6 = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log('排序前:', arr6)
const sortedArr6 = bubbleSort(arr6)
console.log('排序后:', sortedArr6)
// 排序前: [50, 68, 27, 89, 19, 45, 62, 93, 61, 74]
// 冒泡排序耗时: 0.0419921875 ms
// 排序后: [19, 27, 45, 50, 61, 62, 68, 74, 89, 93]

快速排序

思想

• 先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。
• 左右分别用一个空数组去存储比较后的数据。
• 最后递归执行上述操作，直到数组长度 <= 1;

特点：

• 优点：快速，常用。
• 缺点：需要另外声明两个数组，浪费了内存空间资源。

quickSort.ts

function quickSort<T>(arr: T[]): T[] {
  if (!Array.isArray(arr)) return arr

  const length: number = arr.length
  if (length <= 1) return arr

  const pivotIndex = length >> 1
  const pivot = arr.splice(pivotIndex, 1)[0]
  const left: number[] = []
  const right: number[] = []

  for (let i of Object.keys(arr)) {
    arr[i] <= pivot ? left.push(arr[i]) : right.push(arr[i])
  }

  return quickSort(left).concat(pivot, quickSort(right))
}

example

// case1: 普通数组测试
const arr1 = [6, 3, 8, 2, 9, 1]
console.log('排序前:', arr1)
const sortedArr1 = quickSort(arr1)
console.log('排序后:', sortedArr1)
// 排序前: [6, 3, 8, 2, 9, 1]
// 排序后: [1, 2, 3, 6, 8, 9]

// case2: 包含重复元素的数组测试
const arr2 = [9, 3, 6, 2, 6, 1, 9, 4]
console.log('排序前:', arr2)
const sortedArr2 = quickSort(arr2)
console.log('排序后:', sortedArr2)
// 排序前: [9, 3, 6, 2, 6, 1, 9, 4]
// 排序后: [1, 2, 3, 4, 6, 6, 9, 9]

// case3: 空数组测试
const arr3 = []
console.log('排序前:', arr3)
const sortedArr3 = quickSort(arr3)
console.log('排序后:', sortedArr3)
// 排序前: []
// 排序后: []

// case4: 只有一个元素的数组测试
const arr4 = [7]
console.log('排序前:', arr4)
const sortedArr4 = quickSort(arr4)
console.log('排序后:', sortedArr4)
// 排序前: [7]
// 排序后: [7]

// case5: 已经排好序的数组测试
const arr5 = [1, 2, 3, 4, 5]
console.log('排序前:', arr5)
const sortedArr5 = quickSort(arr5)
console.log('排序后:', sortedArr5)
// 排序前: [1, 2, 3, 4, 5]
// 排序后: [1, 2, 3, 4, 5]

// case6: 随机生成数组测试
const arr6 = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log('排序前:', arr6)
const sortedArr6 = quickSort(arr6)
console.log('排序后:', sortedArr6)
// 排序前: [19, 75, 49, 61, 46, 22, 14, 28, 44, 78]
// 排序后: [14, 19, 22, 28, 44, 46, 49, 61, 75, 78]

插入排序

思想：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

insertionSort.ts

function insertionSort<T>(arr: T[]): T[] {
  console.time('插入排序耗时')

  if (!Array.isArray(arr)) return arr

  const length: number = arr.length
  if (length <= 1) return arr

  for (let i = 1; i < length; i++) {
    const current = arr[i]
    let j = i - 1

    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]
      j--
    }

    arr[j + 1] = current
  }

  // for (let i = 1; i < length; i++) {
  //   for (let j = i; j > 0; j--) {
  //     if (arr[j] < arr[j - 1]) {
  //       ;[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
  //     }
  //   }
  // }

  console.timeEnd('插入排序耗时')
  return arr
}

example

// case1: 普通数组测试
const arr1 = [6, 3, 8, 2, 9, 1]
console.log('排序前:', arr1)
const sortedArr1 = insertionSort(arr1)
console.log('排序后:', sortedArr1)
// 排序前: [6, 3, 8, 2, 9, 1]
// 插入排序耗时: 0.01806640625 ms
// 排序后: [1, 2, 3, 6, 8, 9]

// case2: 包含重复元素的数组测试
const arr2 = [9, 3, 6, 2, 6, 1, 9, 4]
console.log('排序前:', arr2)
const sortedArr2 = insertionSort(arr2)
console.log('排序后:', sortedArr2)
// 排序前: [9, 3, 6, 2, 6, 1, 9, 4]
// 插入排序耗时: 0.001953125 ms
// 排序后: [1, 2, 3, 4, 6, 6, 9, 9]

// case3: 空数组测试
const arr3 = []
console.log('排序前:', arr3)
const sortedArr3 = insertionSort(arr3)
console.log('排序后:', sortedArr3)
// 排序前: []
// 排序后: []

// case4: 只有一个元素的数组测试
const arr4 = [7]
console.log('排序前:', arr4)
const sortedArr4 = insertionSort(arr4)
console.log('排序后:', sortedArr4)
// 排序前: [7]
// 排序后: [7]

// case5: 已经排好序的数组测试
const arr5 = [1, 2, 3, 4, 5]
console.log('排序前:', arr5)
const sortedArr5 = insertionSort(arr5)
console.log('排序后:', sortedArr5)
// 排序前: [1, 2, 3, 4, 5]
// 插入排序耗时: 0.48583984375 ms
// 排序后: [1, 2, 3, 4, 5]

// case6: 随机生成数组测试
const arr6 = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log('排序前:', arr6)
const sortedArr6 = insertionSort(arr6)
console.log('排序后:', sortedArr6)
// 排序前: [79, 63, 29, 54, 91, 54, 65, 79, 81, 51]
// 插入排序耗时: 0.004150390625 ms
// 排序后: [29, 51, 54, 54, 63, 65, 79, 79, 81, 91]

希尔排序

https://zh.wikipedia.org/wiki/希尔排序

思想

• 希尔排序将序列分割成若干小序列（逻辑上分组），然后对每一个小序列进行插入排序，此时每一个小序列数据量小，插入排序的效率也提高了。

shellSort.ts

function shellSort<T>(arr: T[]): T[] {
  console.time('希尔排序耗时')

  if (!Array.isArray(arr)) return arr

  const length: number = arr.length
  if (length <= 1) return arr

  let temp
  let step = 1

  let gap = Math.floor(length / 2) // 初始步长为数组长度的一半

  while (gap > 0) {
    // console.log(`Step ${step++}, Gap is ${gap}`)

    for (let i = gap; i < length; i++) {
      temp = arr[i]
      let j = i - gap

      // console.log(`Comparing ${arr[j + gap]} and ${arr[j]}`)

      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j]
        j -= gap
      }

      // console.log(`Moving ${temp} to index ${j + gap}`)
      arr[j + gap] = temp
    }

    gap = Math.floor(gap / 2) // 步长逐渐减半
  }

  console.timeEnd('希尔排序耗时')
  return arr
}

example

// case1: 普通数组测试
const arr1 = [6, 3, 8, 2, 9, 1]
console.log('排序前:', arr1)
const sortedArr1 = shellSort(arr1)
console.log('排序后:', sortedArr1)
// 排序前: [6, 3, 8, 2, 9, 1]
// 插入排序耗时: 0.010009765625 ms
// 排序后: [1, 2, 3, 6, 8, 9]

// case2: 包含重复元素的数组测试
const arr2 = [9, 3, 6, 2, 6, 1, 9, 4]
console.log('排序前:', arr2)
const sortedArr2 = shellSort(arr2)
console.log('排序后:', sortedArr2)
// 排序前: [9, 3, 6, 2, 6, 1, 9, 4]
// 插入排序耗时: 0.022216796875 ms
// 排序后: [1, 2, 3, 4, 6, 6, 9, 9]

// case3: 空数组测试
const arr3 = []
console.log('排序前:', arr3)
const sortedArr3 = shellSort(arr3)
console.log('排序后:', sortedArr3)
// 排序前: []
// 排序后: []

// case4: 只有一个元素的数组测试
const arr4 = [7]
console.log('排序前:', arr4)
const sortedArr4 = shellSort(arr4)
console.log('排序后:', sortedArr4)
// 排序前: [7]
// 排序后: [7]

// case5: 已经排好序的数组测试
const arr5 = [1, 2, 3, 4, 5]
console.log('排序前:', arr5)
const sortedArr5 = shellSort(arr5)
console.log('排序后:', sortedArr5)
// 排序前: [1, 2, 3, 4, 5]
// 插入排序耗时: 0.01611328125 ms
// 排序后: [1, 2, 3, 4, 5]

// case6: 随机生成数组测试
const arr6 = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log('排序前:', arr6)
const sortedArr6 = shellSort(arr6)
console.log('排序后:', sortedArr6)
// 排序前: [14, 2, 22, 63, 37, 90, 92, 80, 26, 76]
// 插入排序耗时: 0.006103515625 ms
// 排序后: [2, 14, 22, 26, 37, 63, 76, 80, 90, 92]

选择排序

思想

• 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

特点

• 优点：上手比较简单，比较符合人的正常思路逻辑。
• 缺点：时间复杂度O(n^2)，运算速度很慢，当数组元素个数比较多时，时间增速惊人。

selectionSort.ts

const selectionSort = (arr) => {
  console.time('选择排序耗时')

  if (!Array.isArray(arr)) return

  const { length } = arr

  for (let i = 0; i < length - 1; i++) {
    let min = arr[i],
      minIndex = i,
      step = 0
    for (let j = i + 1; j < length; j++) {
      step++
      if (min > arr[j]) {
        min = arr[j]
        minIndex = j
      }
    }
    console.log(`Step${i + 1}: ${arr}, min: ${min}, minIndex: ${minIndex}, step: ${step}`)
    ;[arr[i], arr[minIndex]] = [min, arr[i]]
  }

  console.timeEnd('选择排序耗时')
  return arr
}

const array = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log(`原始array: ${array}`)
const newArr = selectionSort(array)
console.log(`selectionSort排序之后newArr: ${newArr}`)

桶排序

计数排序

思想

• 统计每个元素重复出现的次数
• 从小到大按顺序填充数组即可

特点

• 优点：计数排序是所有排序算法中最简单的，也是最符合直觉的算法。
• 缺点：用在待排序数据范围不大的场景，若数据范围 k 比要排序的数据 n 大很多，浪费空间。

function countingSort(arr) {
  console.time('计数排序耗时')

  if (!Array.isArray(arr)) return

  const { length } = arr

  if (length <= 1) return arr

  let counts = [],
    result = []
  let min = Math.min(...arr)
  for (let v of arr) {
    counts[v - min] = (counts[v - min] ?? 0) + 1
  }
  for (let i = 0; i < counts.length; i++) {
    let count = counts[i]
    while (count > 0) {
      result.push(i + min)
      count--
    }
  }

  console.timeEnd('计数排序耗时')
  return result
}

const array = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log(`原始array: ${array}`)
const newArr = countingSort(array)
console.log(`countingSort排序之后newArr: ${newArr}`)

console.log('----------------------------')

// TODO: k远大于n，代码执行久,如下
const array1 = [1, 100000001, 9, 1000, 3000]
console.log(`原始array: ${array1}`)
const newArr1 = countingSort(array1)
console.log(`countingSort排序之后newArr: ${newArr1}`)
// 原始array: 1,100000001,9,1000,3000
// 计数排序耗时: 4.344s
// countingSort排序之后newArr: 1,9,1000,3000,100000001

基数排序

思想

• 基数排序是基于数据位数的一种排序算法。
• 位，是进位的位，比如十进制数的基数是10，就可以按照个十百千万等位来排序。

function radixSort(arr) {
  console.time('基数排序耗时')

  if (!Array.isArray(arr)) return

  let maxLength = 0
  for (let v of arr) {
    const { length } = String(v)
    if (length > maxLength) {
      maxLength = length
    }
  }
  for (i = 0; i < maxLength; i++) {
    arr = sort(arr, i)
  }

  function sort(arr, index) {
    let buckets = []
    for (let i = 0; i < 10; i++) {
      buckets.push([])
    }
    for (let v of arr) {
      let pad = String(v).padStart(maxLength, '0')
      let num = pad[maxLength - 1 - index]
      buckets[num].push(v)
    }
    let result = []
    for (let bucket of buckets) {
      result.push(...bucket)
    }
    return result
  }
  console.timeEnd('基数排序耗时')
  return arr
}

const array = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log(`原始array: ${array}`)
const newArr = radixSort(array)
console.log(`radixSort排序之后newArr: ${newArr}`)

堆排序

归并排序

思想

• "归并" 二字就是"递归"加"合并"。它是典型的分而治之算法。分治思想
• 把数组一分为二，然后递归地排序好每部分，最后合并。

function mergeSort(arr) {
  if (!Array.isArray(arr)) return

  const { length } = arr

  if (length < 2) return arr

  const m = length >> 1,
    left = mergeSort(arr.slice(0, m)),
    right = mergeSort(arr.slice(m))

  let result = []
  let i = 0,
    j = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }
  if (i < left.length) {
    result.push(...left.slice(i))
  } else {
    result.push(...right.slice(j))
  }
  return result
}

const array = Array.from(new Array(10), () => ~~(Math.random() * 100))
console.log(`原始array: ${array}`)
const newArr = mergeSort(array)
console.log(`mergeSort排序之后newArr: ${newArr}`)