排序算法

Illustrated by GAloDos（Pixiv），Source

排序把序列重排为满足给定次序的序列。它看似只是“从小到大”，实际上同时受比较器、数据分布、元素移动成本、稳定性和额外内存约束。算法课关注渐近复杂度，工程实现还必须关心缓存局部性、分支预测、重复键、递归深度，以及比较器是否真的构成全序。

更精确地说，给定序列 $𝐴=\left({𝑎}_0,{𝑎}_1,\dots ,{𝑎}_{𝑛-1}\right)$ 与次序关系 $\le$，排序要产生原序列的一个排列 ${𝐴}^{\prime }=\left({𝑎}_0^{\prime },{𝑎}_1^{\prime },\dots ,{𝑎}_{𝑛-1}^{\prime }\right)$，使任意 $𝑖<𝑗$ 都满足 ${𝑎}_{𝑖}^{\prime }\le {𝑎}_{𝑗}^{\prime }$。这里有两个不能省略的条件：输出必须只重排原元素，不能丢失或凭空增加元素；比较关系必须在整个排序过程中保持一致。许多实现错误只检查“结果递增”，却没有检查元素多重集合是否保持不变。

本章不会把算法当作互不关联的清单。冒泡、选择与插入排序首先展示三种最基本的“扩大有序区”方式；归并、快速与堆排序分别通过分治、划分与堆不变量突破二次复杂度；希尔排序解释如何利用部分有序性；计数、基数与桶排序则通过键域信息绕开纯比较模型。最后再看标准库如何把这些思想组合成现代混合排序。

一、时间复杂度、空间复杂度与稳定性

1. 三个评价维度

时间复杂度应区分最好、平均与最坏情况。插入排序在已有序输入上为 $𝑂\left(𝑛\right)$，一般输入为 $𝑂\left({𝑛}^2\right)$；快速排序平均 $𝑂\left(𝑛log𝑛\right)$，若枢轴持续极端失衡则可退化为 $𝑂\left({𝑛}^2\right)$。只写一个复杂度会掩盖算法最重要的条件。

还要区分比较次数与元素移动次数。对整数排序时，两者代价相近；如果元素是一条很大的记录、比较器需要访问外部字段，或者写入介质寿命有限，二者便可能相差几个数量级。选择排序比较很多但交换很少，归并排序比较有界却需要大量写入辅助数组，间接排序则常只重排记录索引或指针。渐近符号相同并不意味着工程代价相同。

空间复杂度统计输入之外的辅助空间。归并排序通常需要 $𝑂\left(𝑛\right)$ 缓冲区，堆排序只需 $𝑂\left(1\right)$，递归快速排序还要计算调用栈。稳定排序（stable）保证比较结果相等的元素保持原相对次序。例如先按姓名排序，再稳定地按班级排序，同班学生仍保持姓名顺序；若使用不稳定排序，这层次序会丢失。

图 1 稳定排序后，键同为 2 的三个记录仍按原来的 a、b、c 顺序出现。

2. 原地、在线与自适应

原地（in-place）排序只使用常数或对数级辅助空间；在线（online）排序能够随数据到达逐步维护次序；自适应（adaptive）排序会利用已有序片段。它们与稳定性相互独立：堆排序原地但不稳定，归并排序稳定但通常非原地，插入排序既原地又稳定且对近乎有序数据高度自适应。

“原地”也需要说明是否把递归栈算入辅助空间。递归快速排序不申请与 $𝑛$ 同阶的数组，但若极端划分导致调用深度为 $𝑛$，栈空间仍会达到 $𝑂\left(𝑛\right)$；经过短侧递归优化后才可保证 $𝑂\left(log𝑛\right)$ 栈。稳定性同样不是算法名称自动带来的属性：归并时相等元素若优先取右半区，原本稳定的归并排序也会被写成不稳定版本。

3. 比较排序的下界

若算法获得键次序的唯一途径是比较两个元素，可把执行过程看成一棵决策树。每次二元比较至多产生两个分支；要区分 $𝑛$ 个互异元素的 $𝑛!$ 种排列，树必须至少有 $𝑛!$ 个叶子，因此最坏比较次数至少为

归并、堆和良好快速排序达到 $\mathrm{\Theta }\left(𝑛log𝑛\right)$，在比较模型下已是渐近最优。计数排序能够达到 $𝑂\left(𝑛+𝑘\right)$，不是推翻了这个下界，而是额外利用“键是有限范围整数”这一信息，操作不再只有比较。这个区别也是判断能否使用线性时间排序的第一步。

二、冒泡、选择、插入排序

1. 冒泡排序

冒泡排序反复比较相邻元素并交换逆序对。一轮从左到右扫描后，当前最大元素被推到未排序区末端。若一轮没有交换，序列已经有序，可以提前结束。它稳定、原地，最好 $𝑂\left(𝑛\right)$、平均和最坏 $𝑂\left({𝑛}^2\right)$；大量交换使它通常只适合教学或极小输入。

设一轮扫描的右边界为 end。循环不变量是：进入本轮时，区间 a[end+1..] 已经有序，而且其中每个元素都不小于 a[..=end] 中的元素。扫描到位置 i 后，a[i+1] 是原区间 a[..=i+1] 的最大元素；因此扫描结束时，a[end] 必然是当前未排序区的最大值。随后把边界左移一位，不变量继续成立。

相邻交换不会跨越第三个元素。只有严格逆序时才交换，相等记录不会互相越过，所以算法稳定。若把条件误写为 >=，两个相等记录也会交换，稳定性立即丢失。提前结束标记不是单纯的性能技巧：一轮没有交换意味着不存在相邻逆序，而一个序列没有相邻逆序当且仅当它整体非降。

fn bubble_sort<T: Ord>(a: &mut [T]) {
    for end in (1..a.len()).rev() {
        let mut changed = false;
        for i in 0..end {
            if a[i] > a[i + 1] { a.swap(i, i + 1); changed = true; }
        }
        if !changed { break; }
    }
}

2. 选择排序

选择排序每轮从未排序区找最小元素，与区间首元素交换。比较次数固定约为 $\frac{𝑛\left(𝑛-1\right)}{2}$，但交换最多 $𝑛-1$ 次，因此在“比较便宜、写入极贵”的特殊介质上仍有意义。普通交换会让跨越元素改变相对顺序，所以它不稳定。

进入第 i 轮时，前缀 a[..i] 已经是全体元素中最小的 i 个元素，且已经排好序。本轮完整扫描 a[i..] 得到最小值下标 m；交换 a[i] 与 a[m] 后，有序前缀扩大一位。与冒泡不同，无论输入是否已经有序，选择排序仍必须扫描整个未排序区才能证明当前元素确为最小，因此比较次数几乎不受数据分布影响。

它的不稳定性可以用带身份的记录说明：[2a, 2b, 1] 第一轮会交换 2a 与 1，得到 [1, 2b, 2a]，两个键为 2 的记录次序被颠倒。若必须稳定，可把最小元素取出并将中间区间整体右移，但移动次数会上升，已经不是普通的原地选择排序。

fn selection_sort<T: Ord>(a: &mut [T]) {
    for i in 0..a.len() { let mut m=i;
        for j in i+1..a.len() { if a[j] < a[m] { m=j; } }
        if m != i { a.swap(i,m); }
    }
}

3. 插入排序

插入排序维持前缀 a[..i] 已有序，把 a[i] 向左移动到正确位置。其工作量等于逆序对数量：已有序时只比较 $𝑛-1$ 次，逆序时为 $\mathrm{\Theta }\left({𝑛}^2\right)$。短数组、近乎有序数据以及混合排序的递归末端都常用它。

第 i 轮开始时，a[..i] 已经有序。把 a[i] 视为待插入元素，向左比较并越过所有严格大于它的元素，停止处正是保持前缀有序的插入位置。只跨越严格更大的元素意味着它会停在所有相等元素之后，因此稳定。每次相邻交换恰好消除一个逆序对；于是总交换次数精确等于输入逆序对数量，这解释了它为什么会对近乎有序数据表现良好。

教学代码使用 swap 容易看懂，但真实实现常先暂存待插入元素，把较大元素整体右移，最后只写回一次，从而减少写入。还可以在有序前缀中二分寻找插入位置，把比较次数降为 $𝑂\left(𝑛log𝑛\right)$；然而移动次数仍为 $𝑂\left({𝑛}^2\right)$，所以二分插入没有改变整体渐近时间。

fn insertion_sort<T: Ord>(a: &mut [T]) {
    for i in 1..a.len() {
        let mut j = i;
        while j > 0 && a[j] < a[j - 1] { a.swap(j, j - 1); j -= 1; }
    }
}

图 2 三种二次排序分别扩大末尾有序区、选出最小值和扩大前缀有序区。

三者虽然都是 $𝑂\left({𝑛}^2\right)$，适用性并不相同：冒泡排序主要用于展示相邻逆序与稳定性；选择排序在写入次数必须尽量少时才有价值；插入排序因为常数小、局部访问且能利用已有序性，至今仍是混合排序处理中短区间的重要组成部分。

三、归并排序

1. 分解、递归与合并

归并排序把区间递归分成两半，分别排序后用两个指针线性合并。合并阶段每次取两侧首元素中较小者；相等时优先取左侧，稳定性因此得到保持。递归层数为 $log𝑛$，每层处理全部 $𝑛$ 个元素，故时间始终为 $\mathrm{\Theta }\left(𝑛log𝑛\right)$，辅助数组通常为 $𝑂\left(𝑛\right)$。

当区间长度不超过 1 时它天然有序，这是递归基例。长度为 $𝑛$ 的问题产生两个约为 $\frac{𝑛}{2}$ 的子问题，合并需要线性时间，于是递推为

与快速排序不同，分解过程不检查元素值，递归树形状只由长度决定，所以已有序、逆序和随机输入都有相同的渐近界。代价是无论输入多么有序，朴素实现仍会复制和合并每一层；自适应版本会先检查 left.last() <= right.first()，已经整体有序时直接跳过合并。

fn merge_sort<T: Ord + Clone>(a: &mut [T]) {
    let n = a.len(); if n <= 1 { return; }
    let m = n / 2; merge_sort(&mut a[..m]); merge_sort(&mut a[m..]);
    let mut out = Vec::with_capacity(n); let (mut i, mut j) = (0, m);
    while i < m && j < n {
        if a[i] <= a[j] { out.push(a[i].clone()); i += 1; }
        else { out.push(a[j].clone()); j += 1; }
    }
    out.extend_from_slice(&a[i..m]); out.extend_from_slice(&a[j..]);
    a.clone_from_slice(&out);
}

图 3 区间分解到单元素后，自底向上合并相邻有序段。

2. 合并阶段的不变量

设左右有序段分别为 L、R，指针为 i、j。每轮开始时，输出数组恰好包含 L[..i] 与 R[..j] 中的全部元素，并且它们已经有序；尚未输出元素中的最小者必是 L[i] 或 R[j]。取二者较小值便保持不变量，某一侧耗尽后，另一侧剩余部分本身有序，可以整体复制。

稳定性的关键只发生在相等分支。左右两段在原数组中左段整体先于右段；当 L[i] == R[j] 时先输出 L[i]，就保留了原次序。上面代码使用 <= 正是这个原因。若为避免 Clone 而直接移动非 Copy 元素，安全 Rust 实现需要受控的未初始化缓冲区和 panic 安全处理；教学实现选择 Clone，把注意力留给算法不变量。

3. 自底向上、链表与外部排序

链表归并可以通过改接节点完成，无需 $𝑂\left(𝑛\right)$ 元素缓冲；数组归并则有连续访问和缓存友好的优势。自底向上归并以宽度 1、2、4……迭代合并，可消除递归栈，外部排序还可把内存中生成的有序段写入磁盘，再执行多路归并。

自底向上版本先把每个单元素看成有序段，然后依次合并宽度为 1、2、4、8 的相邻段。它仍需合并缓冲区，却没有递归调用，且容易复用同一块内存。外部排序则把“二路”扩展为“多路”：先在内存中分别排序能够容纳的数据块，写成若干磁盘有序段；随后用最小堆保存每个有序段的当前首元素，每次输出最小者并从对应段补入一个元素。此时性能瓶颈是顺序 I/O 次数，而非单纯比较次数。

四、快速排序

1. 枢轴与划分

快速排序选择枢轴，把区间划分为小于、等于和大于枢轴的部分，再递归处理两侧。划分是它的核心：Lomuto 方案简单但重复键与有序输入表现不佳；Hoare 方案交换更少；三路划分能一次聚拢重复键。

划分与归并的方向恰好相反：归并排序先递归得到两个有序段，再花线性时间合并；快速排序先花线性时间建立枢轴两侧的次序关系，随后两个子问题之间不再需要合并。只要划分结束后所有左侧元素不大于枢轴、所有右侧元素不小于枢轴，并把枢轴放到最终位置，递归排序两侧就足以得到全局有序序列。

fn quick_sort<T: Ord>(a: &mut [T]) {
    if a.len() <= 1 { return; }
    let p = a.len() / 2; a.swap(p, a.len() - 1);
    let mut s = 0;
    for i in 0..a.len() - 1 { if a[i] < a[a.len()-1] { a.swap(i, s); s += 1; } }
    a.swap(s, a.len() - 1);
    let (l, r) = a.split_at_mut(s); quick_sort(l); quick_sort(&mut r[1..]);
}

图 4 一次划分建立“小于、等于、大于”三个区间，递归只需进入两侧。

2. Lomuto 不变量与三路划分

上面的代码把枢轴暂存于末尾，并维护边界 s。扫描到 i 之前，a[..s] 全部小于枢轴，a[s..i] 全部不小于枢轴，a[i..last] 尚未分类。遇到小元素便与 a[s] 交换并推进 s；扫描结束再把枢轴交换到 s，其最终位置由此确定。

如果输入含大量与枢轴相等的值，二路划分会把这些值反复送入递归子问题。例如全相等数组在某些实现中每轮只固定一个元素，仍退化为 $𝑂\left({𝑛}^2\right)$。Dutch National Flag 三路划分维护 < pivot、== pivot、未知和 > pivot 四段，完成后等值区无需递归，含 $𝑘$ 种不同键的数据可明显受益。

Hoare 划分则从两端向中间扫描，左指针寻找不小于枢轴的元素，右指针寻找不大于枢轴的元素并交换。它通常比 Lomuto 交换更少，却返回分割边界而非枢轴最终下标；递归区间若照搬 Lomuto 写法，容易出现区间不缩小和无限递归。

3. 复杂度、枢轴选择与栈深度

平均平衡划分给出 $𝑂\left(𝑛log𝑛\right)$，持续选中最小或最大元素会形成深度 $𝑛$ 的递归并退化到 $𝑂\left({𝑛}^2\right)$。随机枢轴、三数取中和三路划分降低退化概率；先递归较短一侧、循环处理较长一侧可把栈控制在 $𝑂\left(log𝑛\right)$。快速排序原地且缓存友好，但交换会破坏相等元素次序。

更具体地，若枢轴最终把长度 $𝑛$ 分为 $𝑘$ 与 $𝑛-𝑘-1$，递推为

当 $𝑘$ 总接近一半时得到 $\mathrm{\Theta }\left(𝑛log𝑛\right)$；当 $𝑘$ 总是 0 时得到 $\mathrm{\Theta }\left({𝑛}^2\right)$。所谓“平均情况”不是所有现实输入自动随机，而是依赖输入排列或枢轴随机性。固定选择首元素会被已有序数据轻易击穿；三数取中改善常见模式，但仍可被专门构造。IntroSort 因此同时记录递归深度，在坏划分累计过多时切换到堆排序。

快速排序不稳定的根源是远距离交换：一个小元素从右侧跨到左侧时可能越过多个等键。可以设计稳定划分，但通常需要额外缓冲，失去传统快速排序原地、常数小的优势。对于必须稳定的记录排序，归并系算法通常更自然。

五、堆排序

1. 从大顶堆得到升序序列

堆排序先用自底向下 sift_down 在 $𝑂\left(𝑛\right)$ 时间内建大顶堆，然后反复把堆顶与末尾交换、缩小堆区并恢复堆。每次取最大值为 $𝑂\left(log𝑛\right)$，总时间在最好、平均和最坏情况下均为 $𝑂\left(𝑛log𝑛\right)$，辅助空间 $𝑂\left(1\right)$。

数组在整个过程中分为活动堆 a[..end] 与有序后缀 a[end..]。循环不变量是：前缀满足大顶堆性质，后缀已经升序排列，且前缀任意元素不大于后缀任意元素。交换堆顶与 a[end-1] 把当前最大值放到最终位置；缩小堆后只有新根可能违反堆性质，一次下沉即可修复。

fn heap_sort<T: Ord>(a: &mut [T]) {
    fn down<T: Ord>(a: &mut [T], mut i: usize, n: usize) {
        loop { let l=2*i+1; if l>=n {break} let r=l+1;
            let c=if r<n && a[r]>a[l]{r}else{l}; if a[i]>=a[c]{break}
            a.swap(i,c); i=c;
        }
    }
    let n=a.len(); for i in (0..n/2).rev(){down(a,i,n)}
    for end in (1..n).rev(){a.swap(0,end);down(a,0,end)}
}

图 5 堆顶最大值与活动区末尾交换；末尾进入有序后缀，剩余前缀重新下沉成堆。

2. 为什么自底向下建堆是线性的

若逐个插入空堆，建堆是 $𝑂\left(𝑛log𝑛\right)$；Floyd 建堆却从最后一个非叶节点向根执行下沉，复杂度为 $𝑂\left(𝑛\right)$。原因是绝大多数节点离叶子很近：约一半节点是叶子，无需下沉；约四分之一至多下降一层；约八分之一至多下降两层。总工作量由

界定，而不是简单地用“$𝑛$ 个节点各做 $log𝑛$”这个过松上界。代码中的 (0..n/2).rev() 正是按从深到浅的顺序处理所有内部节点。

3. 性能特点与稳定性

它提供可靠最坏界，却有跳跃式访存、较多比较且不稳定；因此更常作为 IntroSort 的退化保护，而不是通用数组排序的唯一选择。

下沉会在下标 i、2i+1、4i+3 等位置间跳跃，缓存局部性不如线性扫描的归并与分区；同时每层通常要先比较两个孩子，再比较父子。堆顶与末尾的长距离交换也会改变等键次序，因此堆排序不稳定。它的真正优势是无需 $𝑂\left(𝑛\right)$ 缓冲，又有确定的 $𝑂\left(𝑛log𝑛\right)$ 最坏界；内存紧张或作为混合排序保险时尤其合适。

六、希尔排序

1. 间隔有序与算法过程

希尔排序按递减间隔 $𝑔$ 对若干交错子序列执行插入排序，最后以 $𝑔=1$ 完成普通插入排序。大间隔先消除远距离逆序，使最后一轮移动显著减少。算法原地、代码短，但复杂度强烈依赖间隔序列；简单折半间隔最坏可达 $𝑂\left({𝑛}^2\right)$，更好的经验序列能改善实际表现。跨间隔移动相等元素使它不稳定，理论与可预测性也不如现代混合排序。

所谓 $𝑔$-有序，是指对所有合法下标 $𝑖$ 都有 ${𝑎}_{𝑖}\le {𝑎}_{𝑖+𝑔}$；等价地，从下标 0..g 分别出发、每隔 $𝑔$ 取一个元素得到的各条子序列都已排序。一轮间隔插入结束后，数组成为 $𝑔$-有序。较大的 $𝑔$ 允许一个很小的元素一次跨越很远距离，避免普通插入排序只能逐格左移；最后的 g=1 保证整个数组真正有序。

图 6 同色位置属于同一条间隔子序列；各子序列插入排序后，远距离逆序被提前消除。

fn shell_sort<T: Ord>(a:&mut [T]) { let mut gap=a.len()/2;
    while gap>0 { for i in gap..a.len(){let mut j=i;
        while j>=gap && a[j]<a[j-gap]{a.swap(j,j-gap);j-=gap}
    } gap/=2; }
}

2. 间隔序列与复杂度

代码使用 n/2, n/4, ..., 1 的 Shell 原始序列，便于理解但理论性质并不好。间隔若存在过多公因数，前几轮处理的元素组合高度重复，无法充分混合不同位置。实践中常使用 Knuth 序列 (3^k-1)/2、Ciura 经验序列等；不同序列的最坏界与常数差异很大，因此不能脱离间隔序列笼统地给希尔排序写出唯一复杂度。

即使每个间隔插入都只跨越严格较大元素，不同子序列中的相等元素仍可能在后续轮次改变先后，所以希尔排序通常不稳定。它只需要 $𝑂\left(1\right)$ 辅助空间，曾经适合内存有限的中等数组；现代通用库更偏向具有清晰最坏保证的混合快排或稳定归并系算法。

七、计数排序

1. 从频次到稳定位置

若键是位于小范围 $\left[𝐿,𝑅\right]$ 的整数，可建立长度 $𝑘=𝑅-𝐿+1$ 的计数数组。第一遍统计频次，前缀和把频次转为结束位置，反向扫描输入并写入输出即可保持稳定。时间 $𝑂\left(𝑛+𝑘\right)$、空间 $𝑂\left(𝑘\right)$，与比较排序的 $\mathrm{\Omega }\left(𝑛log𝑛\right)$ 下界不矛盾，因为它利用了键域而非只做比较。

频次数组 count[v] 最初表示键 $𝑣$ 出现多少次。完成前缀和后，它变成“键不大于 $𝑣$ 的元素数量”，也就是键 $𝑣$ 在输出中的右开结束位置。反向扫描输入时先令 count[v] -= 1，所得下标就是当前记录的最终位置。相同键从右到左依次占据其区间的右端，因此输出中的相对次序与输入一致。

fn counting_sort(a: &[usize], max: usize) -> Vec<usize> {
    let mut c=vec![0usize;max+1]; for &x in a {c[x]+=1}
    for i in 1..c.len(){c[i]+=c[i-1]}
    let mut out=vec![0;a.len()]; for &x in a.iter().rev(){c[x]-=1;out[c[x]]=x} out
}

图 7 累计计数给出每个键的输出边界；反向遍历让同键记录保持原来的先后次序。

2. 记录排序、负数与键域成本

当 $𝑘$ 远大于 $𝑛$，清空和遍历计数数组反而浪费；负数可用偏移，巨大稀疏键域则应改用比较排序或先压缩坐标。

示例只输出整数，看不出稳定性的实际用途。若元素是 { key, payload } 记录，计数时只读取 key，放置时复制或移动整条记录；相同 key 的 payload 次序得到保留，这也是计数排序能够成为 LSD 基数排序稳定子过程的原因。

处理范围 [min,max] 时，应先检查 max-min+1 是否溢出以及是否值得分配。若范围是几十亿而只有数千元素，理论表达式 $𝑂\left(𝑛+𝑘\right)$ 已经明确告诉我们它并不快。坐标压缩可把实际出现的不同键映射到较小编号，但建立有序映射本身通常需要排序，不能声称仍是无条件线性时间。

八、基数排序

1. LSD 的循环不变量

基数排序按数字位多轮分配。最低位优先（LSD）从低位到高位，每轮必须稳定，否则高位处理会破坏低位已建立的次序；最高位优先（MSD）先按高位分桶，再递归处理各桶。对固定宽度整数，取基数 $2^{𝑏}$ 可用移位和掩码取位，复杂度为 $𝑂\left(𝑑\left(𝑛+𝑟\right)\right)$，其中 $𝑑$ 为位数、$𝑟$ 为基数。

LSD 的不变量是：完成第 $𝑞$ 轮后，序列已经按最低 $𝑞$ 个数位排序。下一轮按第 $𝑞+1$ 位执行稳定排序；不同高位的元素按新数位分组，同一高位组内仍保持低 $𝑞$ 位次序，于是得到低 $𝑞+1$ 位的正确次序。归纳到最高位便完成全键排序。如果任一轮使用不稳定的分配，相同当前位的元素可能打乱低位次序，归纳立即失效。

图 8 非比较排序把键映射到计数槽、数位桶或值域桶，再按结构顺序收集。

有符号整数需处理符号位；字符串长度不同时还要规定“字符缺失”的次序。基数越大轮数越少，却需要更大的计数表并增加缓存压力。

2. 基数选择与 Rust 实现

下面的 u32 LSD 实现每轮处理一个字节，以 256 个计数槽稳定分配，共执行四轮：

fn radix_sort(a:&mut [u32]) { let mut out=vec![0;a.len()];
    for shift in (0..32).step_by(8) { let mut c=[0usize;256];
        for &x in a.iter(){c[((x>>shift)&255)as usize]+=1}
        for i in 1..256{c[i]+=c[i-1]}
        for &x in a.iter().rev(){let d=((x>>shift)&255)as usize;c[d]-=1;out[c[d]]=x}
        a.copy_from_slice(&out);
    }
}

若改为 i32，直接把补码当 u32 排序会让所有负数位于正数之后的另一端。常见处理是在取最高字节时翻转符号位，等价于把键映射为 (x as u32) ^ 0x8000_0000。字符串 MSD 排序则把“已到字符串末尾”设为比任意字符更小的特殊数位，才能让短前缀排在长字符串之前。

基数 $𝑟=2^{𝑏}$ 增大时，轮数 $𝑑=\frac{𝑤}{𝑏}$ 减少，但每轮需要清零和扫描 $𝑟$ 个计数槽。b=8 的 256 槽通常能留在较小缓存中；一次处理 16 位虽只需两轮，却要维护 65536 个槽。最佳值依赖数据量、缓存和内存带宽，而不是“基数越大越快”。

九、桶排序

1. 值域划分与期望复杂度

桶排序把值域划成若干区间，将元素分配到桶内，分别排序后依桶序连接。若输入近似均匀、桶数与 $𝑛$ 同阶，期望时间可接近 $𝑂\left(𝑛\right)$；若全部元素落入一个桶，复杂度退化为桶内算法的复杂度。它是一套分布框架而非单一实现，边界映射、浮点异常、桶数量和桶内算法都必须结合数据模型选择。

设有 $𝑏$ 个桶，第 $𝑖$ 个桶得到 ${𝑛}_{𝑖}$ 个元素。分配与收集为 $𝑂\left(𝑛+𝑏\right)$；若桶内用插入排序，额外工作约为 ${\sum }_{𝑖}𝑂\left({𝑛}_{𝑖}^2\right)$。均匀分布且 $𝑏=\mathrm{\Theta }\left(𝑛\right)$ 时，每个桶期望只有常数个元素，总期望时间为 $𝑂\left(𝑛\right)$；高度偏斜时某个 ${𝑛}_{𝑖}$ 接近 $𝑛$，便退化为 $𝑂\left({𝑛}^2\right)$。因此桶排序的线性结论是分布假设下的期望，而非所有输入的保证。

2. 映射边界与具体实现

实现时通常用 Vec<Vec<T>> 表示桶，分配后对每个桶调用插入排序或标准排序，最后依次 append。若直接对浮点数计算 floor((x-min)/width)，必须把最大值钳制到最后一个桶，并显式拒绝 NaN；否则边界值会产生越界或不一致次序。

以下代码针对已知属于 [0,1] 且不含 NaN 的 f64。它使用 total_cmp 给桶内浮点数建立全序，并把恰好为 1 的值钳制到最后一个桶：

fn bucket_sort(a:&mut [f64]) {
    let n=a.len(); if n<2{return}
    assert!(a.iter().all(|x|x.is_finite()&&*x>=0.0&&*x<=1.0));
    let mut buckets:Vec<Vec<f64>>=(0..n).map(|_|Vec::new()).collect();
    for &x in a.iter(){let i=((x*n as f64)as usize).min(n-1);buckets[i].push(x)}
    let mut k=0; for b in &mut buckets {b.sort_by(f64::total_cmp);for &x in b.iter(){a[k]=x;k+=1}}
}

若数据分布未知，可先抽样估计分位点，让各桶预计接收近似相同数量，而不是机械等宽划分。并行样本排序正是“采样确定分割点—各线程分桶—桶内排序”的扩展。桶数量太少会让桶内工作过重，太多则增加小数组分配和空桶扫描；工程实现常使用连续缓冲与计数偏移，避免 Vec<Vec<T>> 的大量分配。

十、主流语言中排序算法的实现方式

1. IntroSort

IntroSort 从快速排序开始，递归深度超过阈值便切换堆排序，短区间再用插入排序，从而兼得快速平均性能与 $𝑂\left(𝑛log𝑛\right)$ 最坏保证。C++ std::sort 只规定结果和复杂度，常见实现采用 introspective sorting，但标准不锁定具体算法。[1]

“内省”指算法监视自己的递归行为。初始深度预算通常与 $2\lfloor {log}_2𝑛\rfloor$ 同阶；每完成一次划分便消耗预算。正常情况下快速排序在到达预算前结束，并保留连续分区的良好缓存性能；若坏枢轴让递归过深，剩余区间改用堆排序，切断 $𝑂\left({𝑛}^2\right)$ 路径；区间缩小到十几个或几十个元素后，再用插入排序减少递归、分支和函数调用开销。

IntroSort 并不是“先完整快速排序，失败后重新堆排序”，而是在同一递归框架中对不同区间动态选择。C++ 标准要求 sort 的比较次数为 $𝑂\left(𝑛log𝑛\right)$，但没有规定必须使用 IntroSort；库实现可以采用任何满足语义和复杂度的算法。因此文章可以用 IntroSort 解释常见工程结构，用户代码却不应检测或依赖某个标准库版本的枢轴策略。

2. TimSort

TimSort 扫描输入中的天然升序或降序段 run，短段用插入排序扩展，再按受控规则合并；它稳定且能利用现实数据已有的局部次序。Java 对对象数组的排序保证稳定，常见实现使用 TimSort；基本类型数组则使用双枢轴快速排序，二者不可混称。[2]

扫描时若发现降序 run，会先把它反转成升序；严格降序才可整体反转，否则相等元素也被倒置会破坏稳定性。过短 run 通过二分插入扩展到某个最小长度 minrun，减少后续需要管理的段数。run 被压入栈后并不是等全部扫描完成才任意合并，而是维持相邻长度关系，防止一个巨大 run 与许多极小 run 形成失衡合并树。

归并过程中，如果一侧连续多次胜出，TimSort 会进入 galloping 模式，在另一段中用指数搜索加二分搜索跳过一批元素；局部有序性越强，收益越明显。它的额外空间换来了稳定性和对已有序 run 的自适应。Java Arrays.sort(Object[]) 的公开要求包含稳定性，而基本数值数组不携带可观察的等键身份，因此可使用更节省空间的双枢轴快速排序。算法选择由数据语义而非语言名称决定。

3. pdqSort

Pattern-defeating quicksort 识别会使普通快排退化的模式，并结合无分支划分、坏划分检测与堆排序后备。Rust 当前 sort_unstable 基于 ipnsort，继承快速排序平均性能和堆排序最坏界；稳定的 sort 当前基于 driftsort。实现算法属于版本细节，程序应依赖公开的稳定性、复杂度和内存保证，而非名字。[3]

pdqSort 的出发点是：导致普通快排缓慢的输入往往不是纯随机，而是已有序、逆序、周期重复或持续产生极不平衡划分的模式。算法检测坏划分并扰动少量元素，检测接近有序区间时尝试廉价插入式整理，累计坏划分过多则退回堆排序。它仍是不稳定排序，但把“常见模式”和“对抗性退化”都纳入控制。

Rust 当前不直接把 sort_unstable 文档描述为 pdqSort，而是基于 ipnsort；ipnsort 同样把快速划分的平均性能与最坏后备组合起来，并对低基数、已排序和逆序输入做专门处理。稳定的 slice::sort 使用另一条 driftsort 路线。这里把 pdqSort 单列，是为了说明 pattern-defeating 思想；不能把 pdqSort、ipnsort 和 IntroSort 当作同一个算法的三个名字。

图 9 现代通用排序不会始终执行单一内核：短区间、正常划分与深度超限分别进入适合的处理路径。

4. Rust：稳定 driftsort 与不稳定 ipnsort

Rust 把排序方法定义在切片 [T] 上，因此 Vec<T>、数组和可变切片最终使用同一组实现。接口首先按两个维度拆分：是否稳定，以及次序来自 Ord、比较闭包还是键提取函数。

当前稳定排序 driftsort 结合快速排序的平均性能、归并排序的最坏保证和部分 run 检测。官方文档说明：完全有序或逆序输入可达线性时间；若输入只有 $𝑘$ 个不同值，期望时间为 $𝑂\left(𝑛log𝑘\right)$。它的辅助分配随长度变化：短切片不分配，中等切片申请约 $𝑛$ 个元素的空间，更长输入把缓冲上限钳制在约 $\frac{𝑛}{2}$。这些是当前实现特征，而“稳定、最坏 $𝑂\left(𝑛log𝑛\right)$、原元素在 panic 后仍全部存在”才是调用者应依赖的语义。[3]

当前 sort_unstable 使用 ipnsort：平均路径以快速划分为核心，最坏路径由堆排序思想保护；完全有序和逆序输入同样可线性处理，并对少量不同键给出期望 $𝑂\left(𝑛log𝑘\right)$。它原地且不申请辅助数组，通常比稳定排序快，但“unstable”不是输出随机，而是相等元素的原次序没有保证。

#[derive(Debug)]
struct Student { class: u8, score: u16, serial: u32 }

students.sort_by_key(|s| s.class); // 稳定：同班仍保持此前次序
students.sort_unstable_by(|a,b|
    a.score.cmp(&b.score).then_with(|| a.serial.cmp(&b.serial))
); // 比较器已写出完整次序，不再需要稳定性保存 serial 次序

如果键计算昂贵，例如解析路径、Unicode 归一化或计算摘要，sort_by_key 可能在比较过程中反复求键；sort_by_cached_key 才明确以缓存空间换取每个元素一次键计算。如果只求中位数、百分位数或最小的前 $𝑘$ 个元素，完整排序做了不必要的工作，应考虑 select_nth_unstable 或部分排序接口。

5. Java：基本类型、对象与并行排序分流

Java 的关键不是简单地说“Arrays.sort 使用 TimSort”，因为重载参数类型不同，算法与稳定性也不同。int[]、long[]、double[] 等基本类型数组当前进入 DualPivotQuicksort；Object[] 或带 Comparator 的对象数组要求稳定，当前 OpenJDK 路径使用 ComparableTimSort 或 TimSort。基本类型没有可观察的“两个相等值来自哪条记录”，因此无需为稳定性支付对象搬移缓冲；对象数组则可能依赖等键记录的次级顺序。[2], [4]

双枢轴快速排序一次选择 $𝑝\le 𝑞$ 两个枢轴，把区间划成“小于 $𝑝$”“位于 $𝑝$ 与 $𝑞$ 之间”“大于 $𝑞$”三段。它不是把教科书单枢轴代码机械运行两次，而是在一次扫描中维护多个边界，并对小区间、重复值和不同基本类型采用内部阈值优化。API 文档把具体算法列为 implementation note，未来版本只要保持规范允许更换。

对象 TimSort 会检测天然 run、反转严格降序 run、用二分插入扩展短 run，并按栈不变量合并。OpenJDK 源码中特意把降序定义为严格下降：若把含相等元素的非增 run 整段反转，相等记录次序会颠倒，稳定性便被破坏。短数组走“mini-TimSort”，只做 run 检测与二分插入而不建立完整合并栈。[5]

Arrays.sort(ints);                    // 基本类型：当前为 Dual-Pivot Quicksort 路线
Arrays.sort(records, comparing(R::key)); // 对象：稳定排序
Arrays.parallelSort(largeArray);      // 大数组可使用公共 ForkJoinPool 并行分治
list.sort(comparator);                // List 默认转为数组排序，再写回列表

List.sort 的默认实现先 toArray()，调用数组排序，再通过迭代器把结果写回，因此即使底层是链表也不会在比较时反复按下标遍历；代价是额外对象数组。Arrays.parallelSort 只在规模足够大且并行开销值得时才有优势，小数组最终仍落到串行内核。浮点基本类型按照 Float.compare/Double.compare 所定义的总次序处理 -0.0 与 NaN，不能用普通 < 的直觉代替 API 规则。

6. C++：标准只规定保证，标准库各自选择实现

C++ std::sort 要求随机访问迭代器，排序结果不稳定，并要求 $𝑂\left(𝑁log𝑁\right)$ 次比较；标准没有写“必须使用 IntroSort”。这一区分很重要：IntroSort 是解释常见实现的算法族，std::sort 是由标准约束的接口。std::stable_sort 才保证等价元素保持次序；有足够辅助内存时可做线性额外存储的归并，否则实现可以退回较少内存、更多比较的稳定方案。[1]

GNU libstdc++ 当前源码包含 __introsort_loop，以深度预算控制快速划分，预算耗尽时用堆相关的 partial_sort 路径完成区间，最后执行 __final_insertion_sort 处理短区间。LLVM libc++ 当前同样以 __introsort 为骨架，但组合了块划分、受保护与无保护插入排序、三数取中或 Tukey ninther、完美划分检测等技巧；源码明确说明其中一部分受 pdqSort 启发。两者都满足 std::sort，内部阈值与划分策略却不同。[6], [7]

std::sort(v.begin(), v.end());          // 不稳定，算法由标准库实现决定
std::stable_sort(v.begin(), v.end(), cmp); // 稳定
std::ranges::sort(v, {}, &Record::key); // C++20 projection，按成员键排序
std::nth_element(v.begin(), nth, v.end()); // 只让第 k 个元素就位
std::partial_sort(v.begin(), middle, v.end()); // 只排序最小的前 k 个

如果只需要前 $𝑘$ 小，partial_sort 通常比完整 sort 更符合问题；只需要第 $𝑘$ 个顺序统计量，使用 nth_element。C++17 的执行策略重载可以请求并行执行，但并行版本的调度、额外空间和实际并行度仍由实现决定。比较器必须形成 strict weak ordering；写出 return a <= b 会让 comp(x,x) 为真，破坏算法前提并可能触发越界、错误结果或调试断言。

7. 三种语言的选择结论

可以看到，语言并不是“各自选择一种最佳排序算法”。同一种语言会按稳定性、元素表示、内存和是否并行提供多条路径；同一个 C++ 接口还可能因标准库实现不同而采用不同划分细节。正确的描述应始终包含三层：接口公开保证、当前实现算法、适用工作负载。

十一、总结

排序首先分为比较排序与非比较排序。冒泡、选择、插入属于 $𝑂\left({𝑛}^2\right)$ 级比较排序；归并、快速、堆排序构成 $𝑂\left(𝑛log𝑛\right)$ 主干；希尔排序是间隔插入的特殊比较排序；计数、基数和桶排序利用键域结构突破比较下界。实际选择时先确定是否需要稳定、是否允许辅助空间、键域是否受限，再让标准库的成熟混合算法承担默认工作。

排序算法
├── 比较排序
│   ├── 二次级：冒泡、选择、插入
│   ├── n log n 级：归并、快速、堆
│   └── 特殊改进：希尔与现代混合排序
└── 非比较排序
    ├── 直接使用整个键域：计数排序
    ├── 逐数位建立次序：基数排序
    └── 利用概率分布划分值域：桶排序

选择算法时可以依次提出五个问题：键是否只有有限而稠密的整数范围？是否必须保持等键记录次序？数据能否完全放入内存？输入是否已经包含较长有序段？最坏延迟是否必须有保证？有限键域可能导向计数或基数排序；稳定性与外部数据导向归并系；普通内存数组默认交给标准库不稳定混合排序；近乎有序的小数组适合插入排序；严格最坏界则需要堆排序后备。

最后，手写排序算法主要用于学习、不常见的数据模型或库无法表达的约束。通用业务代码应优先调用标准库，因为成熟实现不仅组合了多个算法，还处理了重复键、零大小类型、panic 安全、临时缓冲复用和平台级优化。理解本章的目的，是能够解释标准库为何这样选择，并在默认假设不成立时作出有根据的替换。