Skip to main content

排序

常见比较排序与非比较排序的思路、复杂度与适用场景。默认讨论升序；代码用 JavaScript 便于对照手写题。

前置：复杂度基础。

1. 排序问题与稳定性​

排序：把序列按关键字排成有序。关键词两个：

概念含义
比较排序靠元素两两比较决定顺序（冒泡、快排、归并…）
非比较排序靠计数、分桶等（计数/桶/基数），有值域或位数前提
稳定性关键字相等时，相对顺序与排序前一致

何时在意稳定性：按多字段排序（先按年龄再按姓名），或相等元素带额外业务含义时。

比较排序的理论下界是 Ω(n log n)（最坏情况下决策树高度），所以「通用、任意可比较类型」时，O(n log n) 已是最优档。

2. 冒泡排序​

相邻两两比较，大的往后冒；一趟后最大的沉到末尾。

  • 时间：最好 O(n)（已有序 + 提前结束），平均/最坏 O(n²)
  • 空间：O(1)
  • 稳定：是
function bubbleSort(arr) {
  const a = arr.slice()
  const n = a.length
  for (let i = 0; i < n - 1; i++) {
    let swapped = false
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }
    if (!swapped) break // 本趟无交换 → 已有序
  }
  return a
}

教学用多；工程上几乎不用。

3. 选择排序​

每趟在未排序区间找最小，与区间首交换。

  • 时间：最好/平均/最坏都是 O(n²)（找最小必须扫完）
  • 空间：O(1)
  • 稳定：否（交换可能打乱相等元素顺序）
function selectionSort(arr) {
  const a = arr.slice()
  const n = a.length
  for (let i = 0; i < n - 1; i++) {
    let min = i
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[min]) min = j
    }
    if (min !== i) [a[i], a[min]] = [a[min], a[i]]
  }
  return a
}

交换次数少（最多 n-1 次），但比较次数仍是平方级。

4. 插入排序​

把当前元素插入到左侧已排好序的区间中合适位置（像摸牌整理）。

  • 时间：最好 O(n)（已有序），平均/最坏 O(n²)
  • 空间：O(1)
  • 稳定：是
function insertionSort(arr) {
  const a = arr.slice()
  for (let i = 1; i < a.length; i++) {
    const cur = a[i]
    let j = i - 1
    while (j >= 0 && a[j] > cur) {
      a[j + 1] = a[j]
      j--
    }
    a[j + 1] = cur
  }
  return a
}

近乎有序或 n 很小（如小于 50）时很快；许多库的快排/归并在小区间会切到插入排序。

5. 归并排序​

分治：对半分 → 递归排序 → 合并两个有序段。

  • 时间：最好/平均/最坏都是 O(n log n)
  • 空间：O(n)（合并要额外数组；递归栈 O(log n)）
  • 稳定：是
function mergeSort(arr) {
  if (arr.length <= 1) return arr.slice()
  const mid = arr.length >> 1
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  const res = []
  let i = 0, j = 0
  while (i < left.length && j < right.length) {
    // <= 保证稳定性：相等时先取左边
    if (left[i] <= right[j]) res.push(left[i++])
    else res.push(right[j++])
  }
  return res.concat(left.slice(i), right.slice(j))
}

特点：性能稳定、稳定排序；代价是额外空间。链表排序、外部排序（大文件）常基于归并思想。

6. 快速排序​

分治：选一个枢轴（pivot），左边都 ≤ 它、右边都 ≥ 它，再递归两侧。

  • 时间：平均 O(n log n)，最坏 O(n²)（已有序 + 总选端点作枢轴）
  • 空间：平均 O(log n) 栈，最坏 O(n)
  • 稳定：否（典型原地分区会打乱）
function quickSort(arr) {
  const a = arr.slice()
  partition(a, 0, a.length - 1)
  return a
}

function partition(a, lo, hi) {
  if (lo >= hi) return
  // 随机枢轴，降低最坏概率
  const pivotIndex = lo + Math.floor(Math.random() * (hi - lo + 1))
  ;[a[pivotIndex], a[hi]] = [a[hi], a[pivotIndex]]
  const pivot = a[hi]
  let i = lo
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      ;[a[i], a[j]] = [a[j], a[i]]
      i++
    }
  }
  ;[a[i], a[hi]] = [a[hi], a[i]]
  partition(a, lo, i - 1)
  partition(a, i + 1, hi)
}

实践中常数小、缓存友好，多数语言默认排序的内核思路之一。工程上会加：随机/三数取中枢轴、小区间改插入、三路快排处理大量重复值。

7. 堆排序​

建大顶堆，反复把堆顶（最大）与末尾交换，再缩小堆并下沉调整。

  • 时间：最好/平均/最坏 O(n log n)（建堆 O(n)，n 次调整各 O(log n)）
  • 空间：O(1)（原地）
  • 稳定：否
function heapSort(arr) {
  const a = arr.slice()
  const n = a.length

  const siftDown = (i, size) => {
    while (true) {
      let largest = i
      const l = i * 2 + 1
      const r = i * 2 + 2
      if (l < size && a[l] > a[largest]) largest = l
      if (r < size && a[r] > a[largest]) largest = r
      if (largest === i) break
      ;[a[i], a[largest]] = [a[largest], a[i]]
      i = largest
    }
  }

  // 建堆：从最后一个非叶节点往上
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n)

  for (let end = n - 1; end > 0; end--) {
    ;[a[0], a[end]] = [a[end], a[0]]
    siftDown(0, end)
  }
  return a
}

保证 O(n log n) 且原地；常数通常比快排大，默认排序较少单独用堆排，但「第 K 大」等题直接用堆更贴切。堆结构见数据结构-堆。

8. 计数排序 / 桶排序 / 基数排序（概览）​

这三类不是靠元素两两比较，在条件满足时可到 O(n + k) 量级（k 与值域或桶数相关）。

计数排序​

统计每个值出现次数，再按值从小到大回填。适合整数且值域不大。

function countingSort(arr) {
  if (arr.length === 0) return []
  const min = Math.min(...arr)
  const max = Math.max(...arr)
  const count = new Array(max - min + 1).fill(0)
  for (const x of arr) count[x - min]++
  const res = []
  for (let i = 0; i < count.length; i++) {
    while (count[i]--) res.push(i + min)
  }
  return res
}
  • 时间 O(n + k)，空间 O(k)，k = max - min + 1
  • 可做成稳定版（常用于基数排序的一趟）

桶排序​

把数据分到若干桶，桶内再排序（插入/递归），最后拼接。数据分布均匀时接近线性。

基数排序​

按位（个位 → 十位 → …，或高位优先）做稳定的计数/桶排序。适合等长数字串、定长字符串。

算法前提要点
计数整数、值域 k 不太大简单、快
桶分布大致均匀桶策略影响很大
基数可拆「位」、位数有限多趟稳定排序

值域巨大或元素不可映射到有限桶时，还是回到比较排序。

9. 各算法对比与选型​

算法平均最坏空间稳定备注
冒泡O(n²)O(n²)O(1)是教学
选择O(n²)O(n²)O(1)否交换少
插入O(n²)O(n²)O(1)是小数组 / 近乎有序
归并O(n log n)O(n log n)O(n)是稳定、性能稳
快排O(n log n)O(n²)O(log n)否实践最快档之一
堆排O(n log n)O(n log n)O(1)否原地保证 n log n
计数等O(n+k)O(n+k)O(k)可有值域前提

选型直觉：

  1. 通用默认：语言内置 sort（多是改进快排 / TimSort 等）
  2. 要稳定 + 保证 n log n：归并（或 TimSort）
  3. 要原地 + 保证 n log n：堆排
  4. 整数且值域小：计数 / 基数
  5. 手写面试：能讲清快排分区与最坏情况、归并合并、堆调整即可

上一篇：复杂度基础 · 下一篇：查找