illegalCreed

中文

English

中文

English

Appearance

三种非比较排序详解 ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 计数排序（Counting Sort）三步：①开 count[0..k] 统计每个值频次；②对 count 做前缀和，此时 count[v] = 「值 ≤ v 的元素个数」= 值 v 在结果中的末尾下标 + 1；③倒序遍历原数组，把每个元素放入 --count[value] 位置——倒序是稳定的关键。
  • 计数排序复杂度：值域 k 时时间 O(n + k)、空间 O(n + k)（结果数组 n + 频次数组 k），稳定；适用前提 k = O(n)，否则空间 / 初始化时间爆炸。
  • 桶排序（Bucket Sort）三步：①把值域 [min, max) 均分成 m 个桶，建桶函数 bucket(x) = ⌊(x - min) / range × m⌋；②每个元素按值落入对应桶，桶内用任意排序（常插排）排好；③按桶号 0→m-1 依序把桶内元素拼回。
  • 桶排序复杂度：均匀分布 + m = Θ(n) 时每桶平均 O(1) 元素，期望 O(n)；输入分布越倾斜退化越严重，最坏退到桶内排序的 O(n²)（全挤一个桶用插排）；稳定性取决于桶内排序是否稳定。
  • 基数排序（Radix Sort）核心：把整数按位分解，LSD（Least Significant Digit）从低位到高位逐位做一趟稳定排序（几乎总用计数排序）；高位排序时，低位已有序的同高位元素靠「稳定性」保持原相对次序。
  • 基数排序复杂度：d 位、基数 b 时 O(d · (n + b)) 时间、O(n + b) 空间，稳定；适用前提：可按位分解、d 不大（固定位数如手机号、定长字符串），否则不适用。
  • 三者对比：计数 = 「值域小整数」；桶 = 「均匀分布浮点」；基数 = 「固定位数整数/字符串」——前提不同，选错就退化。
  • 负数处理：计数排序统一加偏移 x - min 把值域平移到 [0, k)；基数排序负数要分组（负数单独按补码或绝对值处理），通常更推荐计数偏移法。
  • 共同铁律：稳定性是基数排序正确的前提，所以基数排序内部必用稳定排序（计数）；计数排序「倒序放」才稳定。

一、计数排序：频次 → 前缀和 → 定位 ​

计数排序的思想直白且巧妙：既然值域有限，那就数每个值出现几次，再用前缀和把「频次」转成「该值在结果数组里的位置」。

三步流程 ​

假设输入 a 的值域为 [0, k)（若下界非 0，统一减去 min 平移到 [0, k)）。

第一步：统计频次。 开一个长度 k 的 count 数组，扫描 a，count[v]++。

a     = [4, 2, 2, 8, 3, 3, 1]      值域 [0, 9)
count = [0, 1, 2, 2, 1, 0, 0, 0, 1, 0]   // 值 v 出现 count[v] 次

第二步：前缀和。 对 count 做原地前缀和 count[i] += count[i-1]。此时 count[v] 的含义变成了「值 ≤ v 的元素个数」，即值 v 在结果数组中的末尾下标 + 1。

count = [0, 1, 3, 5, 6, 6, 6, 6, 7, 7]   // 值 2 有 3 个 ≤2 的，末尾落在下标 3-1=2

第三步：倒序放置（稳定的关键）。 开结果数组 out，从后往前遍历 a，对每个 a[i]，令 --count[a[i]] 得到它应放的位置，写入 out。倒序保证相同值的元素后出现的仍排在后（稳定）。

倒序扫 a：8→放 out[--count[8]=6]；3→放 out[--count[3]=4]；… 最终稳定。

代码 ​

js
function countingSort(a) {
  if (a.length === 0) return [];
  const min = Math.min(...a), max = Math.max(...a);
  const k = max - min + 1;                 // 值域大小，支持负数
  const count = new Array(k).fill(0);
  for (const x of a) count[x - min]++;     // ① 频次
  for (let i = 1; i < k; i++) count[i] += count[i - 1]; // ② 前缀和 → 末尾下标+1
  const out = new Array(a.length);
  for (let i = a.length - 1; i >= 0; i--) { // ③ 倒序放（稳定）
    out[--count[a[i] - min]] = a[i];
  }
  return out;
}

复杂度分析 ​

  • 时间：①频次 O(n)；②前缀和 O(k)；③放置 O(n)。合计 O(n + k)。
  • 空间：out 长 n + count 长 k，O(n + k)。
  • 稳定性：第三步倒序遍历保证稳定 ✅。
  • 前提：k = O(n) 才划算；k ≫ n（如 32 位整数）时 O(k) 的空间与初始化无法接受。

二、桶排序：分桶 → 桶内排序 → 合并 ​

桶排序的思想是「先把值域切成若干桶，桶间天然有序，桶内各自排好」。当分布均匀时，每个桶元素很少，桶内排序近乎常数，整体期望 O(n)。

三步流程 ​

第一步：分桶。 给定值域 [min, max) 和桶数 m，每个桶负责一段子区间。元素 x 落入桶号 ⌊(x - min) / (max - min) × m⌋（注意 x == max 时单独放最后一个桶避免越界）。

第二步：桶内排序。 每个桶内部用任意排序算法排好——桶内元素少时常用插入排序（小数据量上插排常数小）。

第三步：合并。 按桶号 0 → m-1 依次把桶内元素拼回结果数组。因为桶号本身单调，桶间天然有序，无需归并。

代码（对 [0, 1) 浮点数的经典版本） ​

js
function bucketSort(a, m = a.length) {
  if (a.length === 0) return [];
  const buckets = Array.from({ length: m }, () => []);
  for (const x of a) {
    let idx = Math.floor(x * m);           // [0,1) 浮点 → 桶号
    if (idx === m) idx = m - 1;            // x == 1 边界兜底
    buckets[idx].push(x);
  }
  for (const b of buckets) insertSort(b);  // 桶内插排
  return buckets.flat();                   // 按桶号拼接
}

复杂度分析 ​

  • 期望（均匀分布 + m = Θ(n)）：每桶平均 n/m = O(1) 个元素，桶内插排 O(1)，总桶内 O(n)；分桶 O(n)。合计 期望 O(n)。
  • 最坏（全挤一个桶）：退化为该桶内排序的复杂度，插排时 O(n²)。
  • 空间：桶数组 + 桶内元素，O(n + m)。
  • 稳定性：桶间天然有序；桶内取决于桶内排序是否稳定，用插排则稳定 ✅。

三、基数排序：按位 LSD + 稳定计数排序 ​

基数排序的思想是「按位分解，从低位到高位（LSD）逐位排序，且每一趟必须稳定」。低位的次序在排高位时被稳定性保留，最终得到全局有序。

LSD 流程 ​

以十进制三位数 [329, 457, 657, 839, 436, 720, 355] 为例，按个位、十位、百位各做一趟稳定排序：

初始     按个位     按十位     按百位
329      720        720        329
457      355        355        355
657      436        436        436
839  →   457   →    329   →    457
436      657        457        657
720      329        657        720
355      839        839        839

每一趟用计数排序（以该位数字为关键字），稳定。三趟后整体有序。

代码 ​

js
function radixSort(a) {                       // 非负整数，十进制
  if (a.length === 0) return a;
  const max = Math.max(...a);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingByDigit(a, exp);                  // 每位一趟稳定计数排序
  }
  return a;
}
function countingByDigit(a, exp) {            // 基数 10 的计数排序（原地）
  const count = new Array(10).fill(0);
  for (const x of a) count[digit(x, exp)]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  const out = new Array(a.length);
  for (let i = a.length - 1; i >= 0; i--) {   // 倒序放，稳定
    out[--count[digit(a[i], exp)]] = a[i];
  }
  for (let i = 0; i < a.length; i++) a[i] = out[i];
}
const digit = (x, exp) => Math.floor(x / exp) % 10;

复杂度分析 ​

  • 时间：d 位、基数 b 时共 d 趟，每趟计数排序 O(n + b)，合计 O(d · (n + b))。十进制 d = ⌈log₁₀ max⌉，b = 10；若用基数 b = n 则 d = ⌈logₙ max⌉，时间可写成 O(n)（当 max ≤ nᶜ）。
  • 空间：每趟 out + count，O(n + b)。
  • 稳定性：每趟计数排序倒序放，稳定 ✅——这是 LSD 正确的前提。
  • 前提：可按位分解（整数、定长字符串）、d 不大；浮点数与任意可比较对象不适用。
  • MSD（Most Significant Digit）变体：从高位到低位递归分桶，适合定长字符串字典序，但实现更复杂，且同样要求每层稳定。

四、三者对比表 ​

算法时间空间稳定前提 / 适用
计数排序O(n + k)O(n + k)✅值域 k = O(n) 的整数
桶排序期望 O(n) / 最坏 O(n²)O(n + m)取决桶内值分布近似均匀
基数排序O(d · (n + b))O(n + b)✅可按位分解、d 不大

一句话总结：计数靠值域、桶靠分布、基数靠位数——三者各吃一类「数据特性」，前提满足则线性，不满足则退化或不可用。

交互演示 ​

下一步 ​

掌握了三种算法的内部机制后，下一步是「怎么选」——根据数据特性（值域大小、分布形态、是否固定位数）在三者之间做选型，并认清它们的局限与典型工程应用，见选型与应用场景。