排序算法深度解析

一、排序算法分类总览

比较排序 vs 非比较排序

排序算法按照是否基于元素间的比较操作，可以分为两大类：

┌─────────────────────────────────────────────────────────┐
│                      排序算法                            │
├───────────────────────────┬─────────────────────────────┤
│       比较排序             │       非比较排序             │
│  (基于元素间大小比较)       │  (基于元素的值域特征)        │
├───────────────────────────┼─────────────────────────────┤
│  冒泡排序 Bubble Sort     │  计数排序 Counting Sort     │
│  选择排序 Selection Sort  │  桶排序   Bucket Sort       │
│  插入排序 Insertion Sort  │  基数排序 Radix Sort        │
│  快速排序 Quick Sort      │                             │
│  归并排序 Merge Sort      │                             │
│  堆排序   Heap Sort       │                             │
│  希尔排序 Shell Sort      │                             │
└───────────────────────────┴─────────────────────────────┘

比较排序的理论下界是 O(n log n)（信息论证明：n 个元素的全排列有 n! 种，决策树至少需要 log₂(n!) ≈ n log n 次比较才能区分所有情况）。

非比较排序可以突破 O(n log n) 的下界，在特定条件下达到 O(n) 的线性时间，但通常需要额外的空间开销，且对输入数据有特殊要求（如整数、值域有限等）。

稳定 vs 不稳定

稳定排序：如果两个相等的元素在排序前后的相对顺序保持不变，则该排序算法是稳定的。

不稳定排序：可能改变相等元素的相对顺序。

原始数组: [(A,3), (B,1), (C,3), (D,2)]
按数字排序:

稳定排序结果:   [(B,1), (D,2), (A,3), (C,3)]   ← A 仍在 C 前面 ✓
不稳定排序结果: [(B,1), (D,2), (C,3), (A,3)]   ← A 跑到了 C 后面 ✗

稳定性在多关键字排序时非常重要——先按次要关键字排序，再按主要关键字使用稳定排序，就能得到双关键字有序的结果。

稳定排序: 冒泡、插入、归并、计数、桶、基数
不稳定:   选择、快速、堆、希尔

二、冒泡排序 Bubble Sort

原理

冒泡排序的核心思想是相邻比较，逐步沉底。每一轮遍历都会将当前未排序部分中的最大值"冒泡"到末尾。

ASCII 图解

初始: [5, 3, 8, 1, 2]

第1轮: 相邻比较，最大值 8 冒泡到末尾
  [5, 3, 8, 1, 2]
   5>3 → 交换
  [3, 5, 8, 1, 2]
      5<8 → 不动
  [3, 5, 8, 1, 2]
         8>1 → 交换
  [3, 5, 1, 8, 2]
            8>2 → 交换
  [3, 5, 1, 2, 8]  ← 8 已就位
                 ✓

第2轮: 最大值 5 冒泡到倒数第二位
  [3, 5, 1, 2, | 8]
   3<5 → 不动
  [3, 5, 1, 2, | 8]
      5>1 → 交换
  [3, 1, 5, 2, | 8]
         5>2 → 交换
  [3, 1, 2, 5, | 8]  ← 5 已就位
              ✓

第3轮:
  [3, 1, 2, | 5, 8]
   3>1 → 交换
  [1, 3, 2, | 5, 8]
      3>2 → 交换
  [1, 2, 3, | 5, 8]  ← 3 已就位
           ✓

第4轮:
  [1, 2, | 3, 5, 8]
   1<2 → 不动（本轮无交换，提前终止！）

结果: [1, 2, 3, 5, 8] ✓

完整代码

function bubbleSort(arr: number[]): number[] {
  const n = arr.length
  for (let i = 0; i < n - 1; i++) {
    let swapped = false
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        swapped = true
      }
    }
    if (!swapped) break
  }
  return arr
}

console.log(bubbleSort([5, 3, 8, 1, 2]))

优化：提前终止

上面的代码已经包含了提前终止优化——swapped 标记。如果某一轮遍历中没有发生任何交换，说明数组已经有序，直接 break 退出。

这使得冒泡排序在近乎有序的数组上可以达到 O(n) 的最优时间复杂度。

复杂度分析

维度	复杂度
最好时间	O(n) — 已有序，仅遍历一轮
平均时间	O(n²)
最坏时间	O(n²) — 逆序
空间	O(1)
稳定性	✅ 稳定

三、选择排序 Selection Sort

原理

选择排序的核心思想是每一轮从未排序部分中选出最小值，放到已排序部分的末尾。

ASCII 图解

初始: [29, 10, 14, 37, 13]

第1轮: 从全部元素中找最小值 → 10，与位置 0 交换
  [29, 10, 14, 37, 13]
        ↑ min
  [10, | 29, 14, 37, 13]
   ✓

第2轮: 从位置 1 起找最小值 → 13，与位置 1 交换
  [10, | 29, 14, 37, 13]
                      ↑ min
  [10, 13, | 14, 37, 29]
        ✓

第3轮: 从位置 2 起找最小值 → 14，已在位置 2
  [10, 13, | 14, 37, 29]
             ↑ min
  [10, 13, 14, | 37, 29]
            ✓

第4轮: 从位置 3 起找最小值 → 29，与位置 3 交换
  [10, 13, 14, | 37, 29]
                     ↑ min
  [10, 13, 14, 29, | 37]
                ✓

结果: [10, 13, 14, 29, 37] ✓

完整代码

function selectionSort(arr: number[]): number[] {
  const n = arr.length
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j
      }
    }
    if (minIdx !== i) {
      ;[arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]
    }
  }
  return arr
}

console.log(selectionSort([29, 10, 14, 37, 13]))

复杂度分析

维度	复杂度
最好时间	O(n²) — 即使有序也要全部扫描
平均时间	O(n²)
最坏时间	O(n²)
空间	O(1)
稳定性	❌ 不稳定（交换可能打破相等元素的相对顺序）

四、插入排序 Insertion Sort

原理

插入排序的核心思想类似于打扑克牌时整理手牌——从左到右依次取出每张牌，将它插入到左边已排序部分的正确位置。

ASCII 图解

初始: [5, 2, 4, 6, 1, 3]

第1步: 取出 2，插入到 [5] 中的正确位置
  已排序 | 待排序
  [5]    | [2, 4, 6, 1, 3]    key = 2
   ←── 5>2，5 右移
  [2, 5] | [4, 6, 1, 3]

第2步: 取出 4，插入到 [2, 5] 中
  [2, 5]    | [4, 6, 1, 3]    key = 4
      ←── 5>4，5 右移；2<4，停
  [2, 4, 5] | [6, 1, 3]

第3步: 取出 6，插入到 [2, 4, 5] 中
  [2, 4, 5]    | [6, 1, 3]    key = 6
               5<6，停（已在正确位置）
  [2, 4, 5, 6] | [1, 3]

第4步: 取出 1，插入到 [2, 4, 5, 6] 中
  [2, 4, 5, 6]    | [1, 3]    key = 1
   ←── 全部右移，1 插到最前
  [1, 2, 4, 5, 6] | [3]

第5步: 取出 3，插入到 [1, 2, 4, 5, 6] 中
  [1, 2, 4, 5, 6]    | [3]    key = 3
         ←── 4,5,6 右移；2<3，停
  [1, 2, 3, 4, 5, 6]

结果: [1, 2, 3, 4, 5, 6] ✓

完整代码

function insertionSort(arr: number[]): number[] {
  const n = arr.length
  for (let i = 1; i < n; i++) {
    const key = arr[i]
    let j = i - 1
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = key
  }
  return arr
}

console.log(insertionSort([5, 2, 4, 6, 1, 3]))

为什么小数据量时插入排序最快？

常数因子极小：插入排序的内循环只有比较和赋值，没有函数调用开销，CPU 缓存友好（顺序访问内存）。
对近乎有序的数据极其高效：时间复杂度退化为 O(n)，而快排/归并即使对有序数据也要 O(n log n)。
无递归开销：快排和归并需要递归调用栈，对小数组来说递归开销占比很大。
实践验证：V8 引擎的 TimSort 在子数组长度 ≤ 64 时使用插入排序；Java 的 Arrays.sort() 在长度 ≤ 47 时也切换为插入排序。

复杂度分析

维度	复杂度
最好时间	O(n) — 已有序
平均时间	O(n²)
最坏时间	O(n²) — 逆序
空间	O(1)
稳定性	✅ 稳定

五、快速排序 Quick Sort（重点）

核心思想

快速排序基于分治法：选择一个基准元素（pivot），将数组分为"小于 pivot"和"大于 pivot"两部分，然后递归排序两个子数组。

分区过程 ASCII 图解

初始数组: [3, 6, 8, 10, 1, 2, 1]
选择 pivot = 3（取第一个元素）

Lomuto 分区过程（单向扫描）:
  pivot=3  i=-1
  [3, 6, 8, 10, 1, 2, 1]
   p  j→

  j=1: 6>3  → 跳过
  j=2: 8>3  → 跳过
  j=3: 10>3 → 跳过
  j=4: 1<3  → i++, swap(arr[1],arr[4])
  [3, 1, 8, 10, 6, 2, 1]
      i            j

  j=5: 2<3  → i++, swap(arr[2],arr[5])
  [3, 1, 2, 10, 6, 8, 1]
         i            j

  j=6: 1<3  → i++, swap(arr[3],arr[6])
  [3, 1, 2, 1, 6, 8, 10]
            i            j

  最后: swap(pivot, arr[i]) → swap(arr[0], arr[3])
  [1, 1, 2, 3, 6, 8, 10]
            ↑pivot 就位

  左子数组: [1, 1, 2]    右子数组: [6, 8, 10]
  递归处理...

最终结果: [1, 1, 2, 3, 6, 8, 10] ✓

Lomuto 分区方案

Lomuto 分区使用单指针从左往右扫描，维护一个边界 i，使得 arr[low..i] 中所有元素 ≤ pivot。

function lomutoPartition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]
  let i = low - 1
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
  ;[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]
  return i + 1
}

function quickSortLomuto(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const pi = lomutoPartition(arr, low, high)
    quickSortLomuto(arr, low, pi - 1)
    quickSortLomuto(arr, pi + 1, high)
  }
  return arr
}

console.log(quickSortLomuto([3, 6, 8, 10, 1, 2, 1]))

Hoare 分区方案

Hoare 分区使用双指针从两端向中间夹逼，通常比 Lomuto 交换次数更少（平均少约 3 倍）。

Hoare 分区过程:
  [3, 6, 8, 10, 1, 2, 1]
   ↑                   ↑
   i→                 ←j
  pivot = 3

  i 从左找到 ≥ pivot: i=0 (arr[0]=3)
  j 从右找到 ≤ pivot: j=6 (arr[6]=1)
  swap → [1, 6, 8, 10, 1, 2, 3]

  i 继续: i=1 (arr[1]=6 ≥ 3)
  j 继续: j=5 (arr[5]=2 ≤ 3)
  swap → [1, 2, 8, 10, 1, 6, 3]

  i 继续: i=2 (arr[2]=8 ≥ 3)
  j 继续: j=4 (arr[4]=1 ≤ 3)
  swap → [1, 2, 1, 10, 8, 6, 3]

  i 继续: i=3 (arr[3]=10 ≥ 3)
  j 继续: j=2 (已交叉 j<i)
  返回 j=2

  左子数组: [1, 2, 1]  右子数组: [10, 8, 6, 3]

function hoarePartition(arr: number[], low: number, high: number): number {
  const pivot = arr[Math.floor((low + high) / 2)]
  let i = low - 1
  let j = high + 1
  while (true) {
    do { i++ } while (arr[i] < pivot)
    do { j-- } while (arr[j] > pivot)
    if (i >= j) return j
    ;[arr[i], arr[j]] = [arr[j], arr[i]]
  }
}

function quickSortHoare(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const pi = hoarePartition(arr, low, high)
    quickSortHoare(arr, low, pi)
    quickSortHoare(arr, pi + 1, high)
  }
  return arr
}

console.log(quickSortHoare([3, 6, 8, 10, 1, 2, 1]))

随机化 Pivot

固定选择第一个或最后一个元素作为 pivot，在已排序/逆序数组上会退化为 O(n²)。随机化选择 pivot 可以有效避免最坏情况：

function randomizedQuickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const randomIdx = low + Math.floor(Math.random() * (high - low + 1))
    ;[arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]]
    const pi = lomutoPartition(arr, low, high)
    randomizedQuickSort(arr, low, pi - 1)
    randomizedQuickSort(arr, pi + 1, high)
  }
  return arr
}

console.log(randomizedQuickSort([1, 2, 3, 4, 5, 6, 7, 8]))

三路快排（处理大量重复元素）

当数组中存在大量重复元素时，标准快排仍然会对等于 pivot 的元素做无意义的递归。三路快排将数组分为三个区域：< pivot、= pivot、> pivot，等于 pivot 的元素不再参与后续递归。

三路快排分区过程:
  [3, 5, 2, 3, 8, 3, 1, 3]   pivot = 3

  初始: lt=0, i=0, gt=7
  遍历过程中维护三个区域:
  [  < pivot  |  = pivot  |  未处理  |  > pivot  ]
              lt          i          gt

  i=0: arr[0]=3 = pivot → i++
  [3, | 5, 2, 3, 8, 3, 1, 3]
   lt=0 i=1                gt=7

  i=1: arr[1]=5 > pivot → swap(arr[1],arr[7]), gt--
  [3, 3, 2, 3, 8, 3, 1, | 5]
   lt=0 i=1           gt=6

  i=1: arr[1]=3 = pivot → i++
  [3, 3, | 2, 3, 8, 3, 1, | 5]
   lt=0   i=2           gt=6

  i=2: arr[2]=2 < pivot → swap(arr[0],arr[2]), lt++, i++
  [2, 3, 3, | 3, 8, 3, 1, | 5]
      lt=1   i=3        gt=6

  i=3: arr[3]=3 = pivot → i++
  i=4: arr[4]=8 > pivot → swap(arr[4],arr[6]), gt--
  [2, 3, 3, 3, 1, 3, | 8, 5]
      lt=1      i=4 gt=5

  i=4: arr[4]=1 < pivot → swap(arr[1],arr[4]), lt++, i++
  [2, 1, 3, 3, 3, 3, | 8, 5]
         lt=2      i=5 gt=5

  i=5: arr[5]=3 = pivot → i++
  i=6 > gt=5 → 结束

  结果: [2, 1, | 3, 3, 3, 3, | 8, 5]
          <3      =3 (不递归)    >3

function quickSort3Way(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low >= high) return arr

  const randomIdx = low + Math.floor(Math.random() * (high - low + 1))
  ;[arr[randomIdx], arr[low]] = [arr[low], arr[randomIdx]]

  const pivot = arr[low]
  let lt = low
  let gt = high
  let i = low + 1

  while (i <= gt) {
    if (arr[i] < pivot) {
      ;[arr[lt], arr[i]] = [arr[i], arr[lt]]
      lt++
      i++
    } else if (arr[i] > pivot) {
      ;[arr[i], arr[gt]] = [arr[gt], arr[i]]
      gt--
    } else {
      i++
    }
  }

  quickSort3Way(arr, low, lt - 1)
  quickSort3Way(arr, gt + 1, high)
  return arr
}

console.log(quickSort3Way([3, 5, 2, 3, 8, 3, 1, 3]))

复杂度分析

维度	复杂度	说明
最好时间	O(n log n)	每次 pivot 恰好在中间，将数组等分
平均时间	O(n log n)	随机化 pivot 下期望复杂度
最坏时间	O(n²)	每次 pivot 为最大/最小值，退化为冒泡
空间	O(log n)	递归调用栈深度（最坏 O(n)）
稳定性	❌ 不稳定	分区过程中的交换可能改变相等元素顺序

为什么快排实际性能通常优于归并？

快排是原地排序，空间局部性好，CPU 缓存命中率高
快排的常数因子小于归并（归并需要额外空间 + 复制操作）
随机化后最坏情况概率极低

六、归并排序 Merge Sort（重点）

核心思想

归并排序基于分治法：将数组不断二分，直到每个子数组只有一个元素（天然有序），然后自底向上不断合并两个有序子数组。

分治过程 ASCII 图解

                    [38, 27, 43, 3, 9, 82, 10]
                   /                            \
            [38, 27, 43, 3]              [9, 82, 10]
           /               \             /          \
       [38, 27]         [43, 3]      [9, 82]      [10]
       /      \         /     \      /      \        |
     [38]    [27]    [43]    [3]   [9]    [82]     [10]
       \      /         \     /      \      /        |
       [27, 38]         [3, 43]      [9, 82]       [10]
           \               /             \          /
        [3, 27, 38, 43]              [9, 10, 82]
                   \                     /
             [3, 9, 10, 27, 38, 43, 82]

合并两个有序数组

这是归并排序的核心操作。使用双指针分别指向两个有序数组的开头，每次取较小值放入结果数组。

合并 [3, 27, 38, 43] 和 [9, 10, 82]:

  left:  [3, 27, 38, 43]    right: [9, 10, 82]
          ↑ i=0                      ↑ j=0

  比较 3 vs 9  → 取 3     result: [3]
  比较 27 vs 9 → 取 9     result: [3, 9]
  比较 27 vs 10 → 取 10   result: [3, 9, 10]
  比较 27 vs 82 → 取 27   result: [3, 9, 10, 27]
  比较 38 vs 82 → 取 38   result: [3, 9, 10, 27, 38]
  比较 43 vs 82 → 取 43   result: [3, 9, 10, 27, 38, 43]
  right 剩余 82           result: [3, 9, 10, 27, 38, 43, 82]

自顶向下递归实现

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr

  const mid = Math.floor(arr.length / 2)
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = []
  let i = 0
  let j = 0

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

  while (i < left.length) result.push(left[i++])
  while (j < right.length) result.push(right[j++])

  return result
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]))

原地归并排序（减少空间开销）

上面的实现每次都创建新数组，空间开销较大。可以预分配一个辅助数组来优化：

function mergeSortInPlace(arr: number[]): number[] {
  const aux = new Array(arr.length)
  _mergeSort(arr, aux, 0, arr.length - 1)
  return arr
}

function _mergeSort(arr: number[], aux: number[], low: number, high: number): void {
  if (low >= high) return
  const mid = low + Math.floor((high - low) / 2)
  _mergeSort(arr, aux, low, mid)
  _mergeSort(arr, aux, mid + 1, high)
  _merge(arr, aux, low, mid, high)
}

function _merge(arr: number[], aux: number[], low: number, mid: number, high: number): void {
  for (let k = low; k <= high; k++) {
    aux[k] = arr[k]
  }

  let i = low
  let j = mid + 1

  for (let k = low; k <= high; k++) {
    if (i > mid) {
      arr[k] = aux[j++]
    } else if (j > high) {
      arr[k] = aux[i++]
    } else if (aux[i] <= aux[j]) {
      arr[k] = aux[i++]
    } else {
      arr[k] = aux[j++]
    }
  }
}

console.log(mergeSortInPlace([38, 27, 43, 3, 9, 82, 10]))

应用：逆序对计数

逆序对：在数组中，如果 i < j 且 arr[i] > arr[j]，则 (arr[i], arr[j]) 构成一个逆序对。逆序对的数量衡量了数组的"无序程度"。

归并排序在合并阶段，当右侧元素先被放入结果数组时，说明它比左侧剩余的所有元素都小，此时可以一次性统计多个逆序对。

function countInversions(arr: number[]): number {
  let count = 0

  function mergeSortCount(arr: number[]): number[] {
    if (arr.length <= 1) return arr
    const mid = Math.floor(arr.length / 2)
    const left = mergeSortCount(arr.slice(0, mid))
    const right = mergeSortCount(arr.slice(mid))
    return mergeCount(left, right)
  }

  function mergeCount(left: number[], right: number[]): number[] {
    const result: number[] = []
    let i = 0
    let j = 0

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result.push(left[i++])
      } else {
        count += left.length - i
        result.push(right[j++])
      }
    }

    while (i < left.length) result.push(left[i++])
    while (j < right.length) result.push(right[j++])

    return result
  }

  mergeSortCount(arr)
  return count
}

console.log(countInversions([2, 4, 1, 3, 5]))

复杂度分析

维度	复杂度
最好时间	O(n log n)
平均时间	O(n log n)
最坏时间	O(n log n) — 始终稳定
空间	O(n) — 需要辅助数组
稳定性	✅ 稳定

归并排序的最大优势是时间复杂度始终为 O(n log n)，不会退化。缺点是需要 O(n) 的额外空间。

七、堆排序 Heap Sort

堆的概念

堆是一棵完全二叉树，满足堆性质：

最大堆（Max Heap）：每个节点的值 ≥ 其子节点的值，根节点最大
最小堆（Min Heap）：每个节点的值 ≤ 其子节点的值，根节点最小

堆通常用数组表示，对于索引 i 的节点：

父节点：Math.floor((i - 1) / 2)
左子节点：2 * i + 1
右子节点：2 * i + 2

最大堆示例:
          90
        /    \
      70      80
     /  \    /  \
   50   60  30   20

数组表示: [90, 70, 80, 50, 60, 30, 20]
索引:       0   1   2   3   4   5   6

建堆过程 ASCII 图解

从最后一个非叶子节点开始，自底向上执行 siftDown：

原始数组: [4, 10, 3, 5, 1]

      4
    /   \
   10     3
  /  \
 5    1

最后一个非叶子节点: index = Math.floor(5/2) - 1 = 1 → 元素 10

步骤1: siftDown(index=1)  节点 10
      4
    /   \
   10     3      10 > 5 且 10 > 1，已满足最大堆
  /  \
 5    1           → 不变

步骤2: siftDown(index=0)  节点 4
      4
    /   \
   10     3      子节点最大值 10 > 4
  /  \
 5    1

  → 交换 4 和 10:
      10
    /    \
    4      3     继续 siftDown(index=1): 子节点最大值 5 > 4
  /  \
 5    1

  → 交换 4 和 5:
      10
    /    \
    5      3     4 已是叶子，停止
  /  \
 4    1

建堆完成！数组: [10, 5, 3, 4, 1]

排序过程（不断取出堆顶，放到末尾）:
  [10, 5, 3, 4, 1] → swap(10,1) → [1, 5, 3, 4, | 10] → siftDown → [5, 4, 3, 1, | 10]
  [5, 4, 3, 1, | 10] → swap(5,1) → [1, 4, 3, | 5, 10] → siftDown → [4, 1, 3, | 5, 10]
  [4, 1, 3, | 5, 10] → swap(4,3) → [3, 1, | 4, 5, 10] → siftDown → [3, 1, | 4, 5, 10]
  [3, 1, | 4, 5, 10] → swap(3,1) → [1, | 3, 4, 5, 10]

结果: [1, 3, 4, 5, 10] ✓

siftDown 与 siftUp

siftDown（下沉）：将一个节点与其较大的子节点交换，直到满足堆性质。用于建堆和删除堆顶。

siftUp（上浮）：将一个节点与其父节点交换，直到满足堆性质。用于插入新元素。

完整代码

function heapSort(arr: number[]): number[] {
  const n = arr.length

  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i)
  }

  for (let i = n - 1; i > 0; i--) {
    ;[arr[0], arr[i]] = [arr[i], arr[0]]
    siftDown(arr, i, 0)
  }

  return arr
}

function siftDown(arr: number[], heapSize: number, i: number): void {
  let largest = i
  const left = 2 * i + 1
  const right = 2 * i + 2

  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left
  }
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right
  }

  if (largest !== i) {
    ;[arr[i], arr[largest]] = [arr[largest], arr[i]]
    siftDown(arr, heapSize, largest)
  }
}

function siftUp(arr: number[], i: number): void {
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2)
    if (arr[i] > arr[parent]) {
      ;[arr[i], arr[parent]] = [arr[parent], arr[i]]
      i = parent
    } else {
      break
    }
  }
}

console.log(heapSort([4, 10, 3, 5, 1]))

应用：Top K 问题（LeetCode 215）

题目：给定一个未排序的数组，找到其中第 K 大的元素。

方法一：最小堆（O(n log k)）

维护一个大小为 k 的最小堆。遍历数组，如果当前元素大于堆顶，则替换堆顶并下沉。遍历完成后堆顶就是第 K 大元素。

function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = nums.slice(0, k)

  function siftDown(i: number): void {
    let smallest = i
    const left = 2 * i + 1
    const right = 2 * i + 2
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right
    if (smallest !== i) {
      ;[heap[i], heap[smallest]] = [heap[smallest], heap[i]]
      siftDown(smallest)
    }
  }

  for (let i = Math.floor(k / 2) - 1; i >= 0; i--) {
    siftDown(i)
  }

  for (let i = k; i < nums.length; i++) {
    if (nums[i] > heap[0]) {
      heap[0] = nums[i]
      siftDown(0)
    }
  }

  return heap[0]
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2))

方法二：快速选择（O(n) 平均）

基于快排的分区思想，只需要递归处理包含目标位置的那一半：

function findKthLargestQuickSelect(nums: number[], k: number): number {
  const target = nums.length - k

  function quickSelect(low: number, high: number): number {
    const randomIdx = low + Math.floor(Math.random() * (high - low + 1))
    ;[nums[randomIdx], nums[high]] = [nums[high], nums[randomIdx]]

    const pivot = nums[high]
    let i = low - 1
    for (let j = low; j < high; j++) {
      if (nums[j] <= pivot) {
        i++
        ;[nums[i], nums[j]] = [nums[j], nums[i]]
      }
    }
    ;[nums[i + 1], nums[high]] = [nums[high], nums[i + 1]]
    const pi = i + 1

    if (pi === target) return nums[pi]
    if (pi < target) return quickSelect(pi + 1, high)
    return quickSelect(low, pi - 1)
  }

  return quickSelect(0, nums.length - 1)
}

console.log(findKthLargestQuickSelect([3, 2, 1, 5, 6, 4], 2))

复杂度分析

维度	复杂度
最好时间	O(n log n)
平均时间	O(n log n)
最坏时间	O(n log n) — 始终稳定
空间	O(1) — 原地排序
稳定性	❌ 不稳定

堆排序的优势在于时间复杂度稳定 + 原地排序，是唯一同时满足这两点的排序算法。缺点是缓存不友好（数组中跳跃访问），实际性能通常不如快排。

八、计数排序 / 桶排序 / 基数排序

计数排序 Counting Sort

原理：统计每个元素出现的次数，然后根据计数信息直接将元素放到正确位置。

适用场景：元素为整数且值域范围 k 不大（k = O(n)）时，时间复杂度为 O(n + k)。

function countingSort(arr: number[]): number[] {
  if (arr.length === 0) return arr

  const max = Math.max(...arr)
  const min = Math.min(...arr)
  const range = max - min + 1
  const count = new Array(range).fill(0)
  const output = new Array(arr.length)

  for (const num of arr) {
    count[num - min]++
  }

  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1]
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i]
    count[arr[i] - min]--
  }

  return output
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1]))

桶排序 Bucket Sort

原理：将元素分散到若干个"桶"中，每个桶内单独排序，最后将所有桶按顺序合并。

适用场景：数据分布均匀时效果最好，例如 [0, 1) 之间的浮点数。

function bucketSort(arr: number[], bucketCount = 5): number[] {
  if (arr.length === 0) return arr

  const max = Math.max(...arr)
  const min = Math.min(...arr)

  const bucketSize = (max - min) / bucketCount + 1
  const buckets: number[][] = Array.from({ length: bucketCount }, () => [])

  for (const num of arr) {
    const idx = Math.floor((num - min) / bucketSize)
    buckets[idx].push(num)
  }

  const result: number[] = []
  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b)
    result.push(...bucket)
  }

  return result
}

console.log(bucketSort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]))

基数排序 Radix Sort

原理：按位排序（从低位到高位），每一轮使用稳定排序（如计数排序）对当前位进行排序。

适用场景：整数或定长字符串排序，元素最大位数 d 较小时，时间复杂度为 O(d × (n + k))。

function radixSort(arr: number[]): number[] {
  if (arr.length === 0) return arr

  const max = Math.max(...arr)

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp)
  }

  return arr
}

function countingSortByDigit(arr: number[], exp: number): void {
  const n = arr.length
  const output = new Array(n)
  const count = new Array(10).fill(0)

  for (const num of arr) {
    const digit = Math.floor(num / exp) % 10
    count[digit]++
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1]
  }

  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10
    output[count[digit] - 1] = arr[i]
    count[digit]--
  }

  for (let i = 0; i < n; i++) {
    arr[i] = output[i]
  }
}

console.log(radixSort([170, 45, 75, 90, 802, 24, 2, 66]))

九、排序算法完整对比表

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

k：值域范围（计数/桶排序）或基数（基数排序中通常为 10）
d：最大元素的位数（基数排序）

如何选择排序算法？

数据量小（n ≤ 50）                    → 插入排序
数据基本有序                           → 插入排序 / TimSort
数据量大 + 需要稳定排序                 → 归并排序
数据量大 + 不要求稳定 + 需要原地排序      → 快速排序（随机化）/ 堆排序
数据为整数且值域不大                     → 计数排序
数据为整数且位数固定                     → 基数排序
数据分布均匀                           → 桶排序

十、V8 的 Array.sort() 实现：TimSort 算法简介

从 V8 v7.0（Chrome 70）起，Array.prototype.sort() 采用 TimSort 算法，替代了之前的快速排序实现。

TimSort 核心思想

TimSort 是一种混合排序算法，由 Tim Peters 于 2002 年为 Python 设计，结合了归并排序和插入排序的优势：

1. 寻找自然有序片段（Run）

TimSort 首先扫描数组，识别已经有序（升序或降序）的片段，称为 run。如果 run 太短（小于 minrun，通常为 32-64），则使用插入排序将其扩展到 minrun 长度。

原始数组: [3, 5, 8, 2, 1, 9, 7, 4, 6, 10]

识别 run:
  Run 1: [3, 5, 8]       ← 自然升序
  Run 2: [2, 1] → [1, 2] ← 自然降序，翻转
  Run 3: [9]              ← 太短，用插入排序扩展
  ...

扩展后的 runs 被压入栈中

2. 归并策略

将 run 压入栈中，通过维护栈不变式来决定何时合并相邻的 run：

栈不变式:
  对于栈顶的三个 run A、B、C（C 在栈底）:
  1. |C| > |B| + |A|
  2. |B| > |A|

  如果违反任一条件，则合并较小的相邻 run

3. 优化的合并（Galloping Mode）

合并时使用飞奔模式：如果连续多个元素来自同一个 run，就用二分查找跳过大段元素，减少比较次数。

为什么 TimSort 优于单一排序算法？

特性	说明
自适应	利用数据中已有的有序性，近乎有序的数据接近 O(n)
稳定	基于归并排序，保证稳定性
最坏 O(n log n)	不会退化
小数组优化	使用插入排序处理小片段
实践验证	Python、Java、V8、Rust 标准库都采用 TimSort

十一、面试题精选（5 道 · 含详细解答）

题目 1：实现一个排序算法，时间 O(n log n)，空间 O(1)，且稳定

解答：这是一个经典的不可能三角——目前没有已知的排序算法能同时满足这三个条件。

归并排序：O(n log n) + 稳定，但空间 O(n)
堆排序：O(n log n) + O(1)，但不稳定
快速排序：O(n log n) 平均 + O(log n)，但不稳定且最坏 O(n²)

如果面试中遇到这个问题，正确的回答是：无法同时满足。可以退而求其次：

如果可以接受 O(n) 空间 → 归并排序
如果可以接受不稳定 → 堆排序
Block Sort（WikiSort）理论上可以做到 O(n log n) + O(1) + 稳定，但实现极其复杂，常数因子大

题目 2：给定一个几乎有序的数组（每个元素离最终位置不超过 k），最优排序方法？

解答：使用大小为 k+1 的最小堆。

function sortNearlySorted(arr: number[], k: number): number[] {
  const result: number[] = []
  const heap: number[] = []

  function pushHeap(val: number): void {
    heap.push(val)
    let i = heap.length - 1
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2)
      if (heap[i] < heap[parent]) {
        ;[heap[i], heap[parent]] = [heap[parent], heap[i]]
        i = parent
      } else break
    }
  }

  function popHeap(): number {
    const min = heap[0]
    const last = heap.pop()!
    if (heap.length > 0) {
      heap[0] = last
      let i = 0
      while (true) {
        let smallest = i
        const left = 2 * i + 1
        const right = 2 * i + 2
        if (left < heap.length && heap[left] < heap[smallest]) smallest = left
        if (right < heap.length && heap[right] < heap[smallest]) smallest = right
        if (smallest === i) break
        ;[heap[i], heap[smallest]] = [heap[smallest], heap[i]]
        i = smallest
      }
    }
    return min
  }

  for (let i = 0; i <= Math.min(k, arr.length - 1); i++) {
    pushHeap(arr[i])
  }

  for (let i = k + 1; i < arr.length; i++) {
    result.push(popHeap())
    pushHeap(arr[i])
  }

  while (heap.length > 0) {
    result.push(popHeap())
  }

  return result
}

console.log(sortNearlySorted([6, 5, 3, 2, 8, 10, 9], 3))

时间复杂度：O(n log k)，当 k 远小于 n 时远优于 O(n log n)。

题目 3：如何对一个包含大量重复元素的数组排序？分析不同方案的优劣

解答：

方案 A：三路快排 — 最佳选择

将等于 pivot 的元素聚集在中间，不再参与后续递归。当重复元素多时，每次分区能排除大量元素。

方案 B：计数排序 — 如果值域范围小

如果元素值域范围有限（如 0-100 之间的成绩），计数排序 O(n + k) 更优。

方案 C：标准快排 — 最差选择

大量相等元素导致分区极度不均衡，时间退化为 O(n²)。

function sortWithDuplicates(arr: number[]): number[] {
  return quickSort3Way([...arr])
}

function quickSort3Way(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low >= high) return arr

  const randomIdx = low + Math.floor(Math.random() * (high - low + 1))
  ;[arr[randomIdx], arr[low]] = [arr[low], arr[randomIdx]]

  const pivot = arr[low]
  let lt = low, gt = high, i = low + 1

  while (i <= gt) {
    if (arr[i] < pivot) {
      ;[arr[lt], arr[i]] = [arr[i], arr[lt]]
      lt++
      i++
    } else if (arr[i] > pivot) {
      ;[arr[i], arr[gt]] = [arr[gt], arr[i]]
      gt--
    } else {
      i++
    }
  }

  quickSort3Way(arr, low, lt - 1)
  quickSort3Way(arr, gt + 1, high)
  return arr
}

console.log(sortWithDuplicates([3, 3, 3, 1, 1, 2, 2, 2, 3, 1]))

题目 4：不使用额外空间，如何合并两个已排序的数组（第一个数组末尾有足够空间）？

解答：从后往前填充。这是 LeetCode 88 的经典解法。

function mergeSortedArrays(nums1: number[], m: number, nums2: number[], n: number): void {
  let p1 = m - 1
  let p2 = n - 1
  let p = m + n - 1

  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1]
      p1--
    } else {
      nums1[p] = nums2[p2]
      p2--
    }
    p--
  }

  while (p2 >= 0) {
    nums1[p] = nums2[p2]
    p2--
    p--
  }
}

const nums1 = [1, 2, 3, 0, 0, 0]
mergeSortedArrays(nums1, 3, [2, 5, 6], 3)
console.log(nums1)

从后往前的关键洞察：最大的元素一定在两个数组的末尾，填充到 nums1 的末尾不会覆盖尚未处理的元素。

题目 5：实现一个排序算法，能在 O(n) 时间内对 [0, n²) 范围内的 n 个整数排序

解答：使用基数排序，以 n 为基数。

每个数可以表示为 a * n + b（其中 0 ≤ a, b < n），相当于最多 2 位的 n 进制数。对每一位执行计数排序（O(n + n) = O(n)），总共 2 轮，时间复杂度 O(2 × (n + n)) = O(n)。

function sortInRangeN2(arr: number[], n: number): number[] {
  const sortByDigit = (arr: number[], base: number, exp: number): number[] => {
    const count = new Array(base).fill(0)
    const output = new Array(arr.length)

    for (const num of arr) {
      const digit = Math.floor(num / exp) % base
      count[digit]++
    }

    for (let i = 1; i < base; i++) {
      count[i] += count[i - 1]
    }

    for (let i = arr.length - 1; i >= 0; i--) {
      const digit = Math.floor(arr[i] / exp) % base
      output[count[digit] - 1] = arr[i]
      count[digit]--
    }

    return output
  }

  let result = sortByDigit(arr, n, 1)
  result = sortByDigit(result, n, n)
  return result
}

console.log(sortInRangeN2([7, 15, 3, 12, 0, 8, 1], 4))

十二、追问思考（5 道）

为什么快速排序在实际工程中比堆排序更受欢迎？ 从 CPU 缓存局部性、分支预测、常数因子等角度分析。
归并排序的自底向上（迭代）实现相比自顶向下（递归）实现有哪些优势和劣势？ 尝试用迭代方式实现归并排序，并分析空间复杂度的差异。
如何证明比较排序的时间复杂度下界是 Ω(n log n)？ 从决策树模型出发，解释为什么 n 个元素的排序需要至少 log₂(n!) 次比较。
在并行/多核场景下，哪种排序算法最适合并行化？ 对比快排、归并排序、基数排序的并行化策略和难点。
如何设计一个外部排序算法来排序 100GB 的文件（内存只有 1GB）？ 描述多路归并的思路，以及如何利用堆来优化合并过程。

排序算法深度解析 ​

一、排序算法分类总览 ​

比较排序 vs 非比较排序 ​

稳定 vs 不稳定 ​

二、冒泡排序 Bubble Sort ​

原理 ​

ASCII 图解 ​

完整代码 ​

优化：提前终止 ​

复杂度分析 ​

三、选择排序 Selection Sort ​

原理 ​

ASCII 图解 ​

完整代码 ​

复杂度分析 ​

四、插入排序 Insertion Sort ​

原理 ​

ASCII 图解 ​

完整代码 ​

为什么小数据量时插入排序最快？ ​

复杂度分析 ​

五、快速排序 Quick Sort（重点） ​

核心思想 ​

分区过程 ASCII 图解 ​

Lomuto 分区方案 ​

Hoare 分区方案 ​

随机化 Pivot ​

三路快排（处理大量重复元素） ​

复杂度分析 ​

六、归并排序 Merge Sort（重点） ​

核心思想 ​

分治过程 ASCII 图解 ​

合并两个有序数组 ​

自顶向下递归实现 ​

原地归并排序（减少空间开销） ​

应用：逆序对计数 ​

复杂度分析 ​

七、堆排序 Heap Sort ​

堆的概念 ​

建堆过程 ASCII 图解 ​

siftDown 与 siftUp ​

完整代码 ​

应用：Top K 问题（LeetCode 215） ​

复杂度分析 ​

八、计数排序 / 桶排序 / 基数排序 ​

计数排序 Counting Sort ​

桶排序 Bucket Sort ​

基数排序 Radix Sort ​

九、排序算法完整对比表 ​

十、V8 的 Array.sort() 实现：TimSort 算法简介 ​

TimSort 核心思想 ​

为什么 TimSort 优于单一排序算法？ ​

十一、面试题精选（5 道 · 含详细解答） ​

题目 1：实现一个排序算法，时间 O(n log n)，空间 O(1)，且稳定 ​

题目 2：给定一个几乎有序的数组（每个元素离最终位置不超过 k），最优排序方法？ ​

题目 3：如何对一个包含大量重复元素的数组排序？分析不同方案的优劣 ​

题目 4：不使用额外空间，如何合并两个已排序的数组（第一个数组末尾有足够空间）？ ​

题目 5：实现一个排序算法，能在 O(n) 时间内对 [0, n²) 范围内的 n 个整数排序 ​

十二、追问思考（5 道） ​

排序算法深度解析

一、排序算法分类总览

比较排序 vs 非比较排序

稳定 vs 不稳定

二、冒泡排序 Bubble Sort

原理

ASCII 图解

完整代码

优化：提前终止

复杂度分析

三、选择排序 Selection Sort

原理

ASCII 图解

完整代码

复杂度分析

四、插入排序 Insertion Sort

原理

ASCII 图解

完整代码

为什么小数据量时插入排序最快？

复杂度分析

五、快速排序 Quick Sort（重点）

核心思想

分区过程 ASCII 图解

Lomuto 分区方案

Hoare 分区方案

随机化 Pivot

三路快排（处理大量重复元素）

复杂度分析

六、归并排序 Merge Sort（重点）

核心思想

分治过程 ASCII 图解

合并两个有序数组

自顶向下递归实现

原地归并排序（减少空间开销）

应用：逆序对计数

复杂度分析

七、堆排序 Heap Sort

堆的概念

建堆过程 ASCII 图解

siftDown 与 siftUp

完整代码

应用：Top K 问题（LeetCode 215）

复杂度分析

八、计数排序 / 桶排序 / 基数排序

计数排序 Counting Sort

桶排序 Bucket Sort

基数排序 Radix Sort

九、排序算法完整对比表

十、V8 的 Array.sort() 实现：TimSort 算法简介

TimSort 核心思想

为什么 TimSort 优于单一排序算法？

十一、面试题精选（5 道 · 含详细解答）

题目 1：实现一个排序算法，时间 O(n log n)，空间 O(1)，且稳定

题目 2：给定一个几乎有序的数组（每个元素离最终位置不超过 k），最优排序方法？

题目 3：如何对一个包含大量重复元素的数组排序？分析不同方案的优劣

题目 4：不使用额外空间，如何合并两个已排序的数组（第一个数组末尾有足够空间）？

题目 5：实现一个排序算法，能在 O(n) 时间内对 [0, n²) 范围内的 n 个整数排序

十二、追问思考（5 道）