2.1 Elementary Sorts：选择、插入与希尔排序

2.1 · Elementary Sorts覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

能解释“2.1 · Elementary Sorts”如何用选择、插入和希尔排序的交换轨迹解释局部有序度、成本与适用输入
能逐项核对初级排序、选择排序、插入排序、排序可视化、希尔排序，并区分作者站内容与本页独立补充
能按“选择排序比较约 N^2/2 次；插入排序交换数等于输入逆序对数”手算一个最小输入，逐步检查“每轮结束后声明的前缀、后缀或 h-子序列必须有序，元素多重集保持不变”
能注入“插入时把比较边界写成 j > 0 却读取 a[j-1] 之外的位置，或遗漏最后一个 h=1”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“2·1 · Elementary Sorts”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“2·1 · Elementary Sorts”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“2·1 · Elementary Sorts”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：2.1 · Elementary Sorts

1. 初级排序：在本页通过“选择算法与 h”连接解释、交互状态和练习验收。
2. 选择排序：在本页通过“定位局部逆序”连接解释、交互状态和练习验收。
3. 插入排序：在本页通过“移动或交换元素”连接解释、交互状态和练习验收。
4. 排序可视化：在本页通过“扩大有序区域”连接解释、交互状态和练习验收。
5. 希尔排序：在本页通过“核对全序和多重集”连接解释、交互状态和练习验收。

从“比较便宜，但搬动很贵”开始

初级排序（elementary sorts）不是只为记住三段循环。假设仓库中的箱子只需读标签就能比较，却要用叉车才能交换；选择排序固定做平方级比较，却只做线性次交换，可能优于会频繁搬动的插入排序。再假设输入几乎有序，插入排序只消去很少的逆序，成本又可能接近线性。

先预测数组已经升序时，选择排序会不会因为“看见有序”而提前结束。官方实现不会：第i轮仍扫描整个后缀来证明当前位置是剩余最小项。插入排序则在第一次相邻比较失败时停止内循环。因此算法名称相近，成本对input order的敏感性却完全不同。

官方2.1依次讨论 Rules of the game、Selection sort、Insertion sort、Visualizing sorting algorithms、Shellsort。贯穿它们的是同一sort contract：输出必须非降序、必须是输入的permutation，并在声明稳定时保留equal keys的相对次序。

2.1.1 Rules of the game：先固定排序契约

排序契约（sorting contract）把“如何排”与“什么叫排对”分开。Java Comparable 的 compareTo 必须表达total order：reflexive、antisymmetric、transitive；null或不兼容类型应失败，而不是给出随意顺序。

官方交换式实现通常只通过 less 与 exch 观察和改动数据：

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}
 
private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

成本模型（sorting cost model）不能只写Big-O。对交换式算法分别数compares和exchanges，才能回答“比较贵还是搬动贵”；不使用交换的实现则常数array accesses。原地排序（in-place）只用常数local storage或很小的调用栈，不再分配一份N项副本。

正确性oracle至少包含两个独立检查。第一，逐相邻项验证非降序；第二，对输入和输出建立frequency map，验证没有丢失、复制或改写元素。只跑 isSorted 无法发现一个错误实现把所有元素都改成最小值。

2.1.2 Selection sort：固定最小前缀

选择排序（selection sort）维护不变量：进入第i轮时，a[0..i) 已是全局最小的i项且有序；扫描 a[i..N) 找到minimum后交换到i，不变量扩大一项。

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (less(a[j], a[min])) min = j;
        exch(a, i, min);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

第i轮比较 N-i-1 次，输入排列不会改变总数：

C_{\mathrm{selection}}(N) =\sum_{i=0}^{N-1}(N-i-1) =\frac{N(N-1)}{2} \sim\frac{N^2}{2}

当前官方loop执行N次 exch，其中最后一轮以及某些minimum已在i处的轮次是self-exchange；若只计真正搬动，可以跳过 min == i，但比较仍是平方级。算法额外空间为Theta(1)，通常不稳定：远距离交换可能让两个相等key颠倒原相对次序。

2.1.3 Insertion sort：逆序数就是搬动量

插入排序（insertion sort）维护另一种不变量：进入第i轮前 a[0..i) 已有序；当前项向左跨过所有更大项，停止时 a[0..i] 有序。严格 less(a[j], a[j-1]) 不交换equal keys，因此官方版本稳定。

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && less(a[j], a[j - 1]); j--)
            exch(a, j, j - 1);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

逆序（inversion）把“几乎有序”变成精确参数：

I(A)=\left|\{(i,j)\mid i\lt j,\ a_i\gt a_j\}\right|

每次相邻逆序交换恰好消去一个逆序，也不会新建其他逆序，所以插入排序的exchanges恰等于I。每轮成功交换对应一次true compare，最后还可能有一次停止比较，因此：

I(A)\le C_{\mathrm{insertion}}(A)\le I(A)+N-1

升序输入有I等于0，使用N-1次比较、0次交换；逆序且keys distinct时I等于 N(N-1)/2，比较和交换都约为N平方的一半。随机distinct排列平均每对有一半概率逆序，因此平均比较与交换都约为N平方的四分之一。若I只是不超过cN，算法就是linear scale，正是它适合部分有序大数组的原因。

2.1.4 Sorting visualization：看见移动，但仍要证明

排序可视化（sorting visualization）把每个key画成一根竖条。选择排序的左侧短条逐轮固定，右侧仍保留原来的混乱；插入排序的左侧始终有序，但每次插入会让局部柱条连续右移。

图像适合发现“minimum是否真的进入边界”“插入是否跨过equal key”“某轮是否漏扫”，却不是correctness proof。两个不同输入可能产生相似图形，低分辨率还会把相等与接近的key混在一起。验收需要把visual trace和machine-checkable invariant绑定：每帧检查prefix、每次交换检查permutation、终帧检查全序。

稳定性（stability）对只画key高度的图尤其容易被隐藏。应给equal keys附加原始标签，例如2A与2B；如果高度相等但标签顺序逆转，结果虽然nondecreasing，却不满足stable contract。

2.1.5 Shellsort：先跨远距离，再用局部插入收尾

希尔排序（Shellsort）扩展插入排序：先允许相距h的项交换，让远离目标位置的项大步移动；再逐渐缩小h。数组若从任意起点每隔h取出的subsequence都已排序，就称为h有序。

h有序（h-sorted）可以看成h条交错的sorted subsequences。任意以1结尾的gap sequence最终都能完成排序，因为1-sorted恰好就是全局sorted。

public static void sort(Comparable[] a) {
    int n = a.length;
    int h = 1;
    while (h < n / 3) h = 3 * h + 1;
 
    while (h >= 1) {
        for (int i = h; i < n; i++)
            for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                exch(a, j, j - h);
        h /= 3;
    }
}

官方实现使用Knuth increments：

h_k=\frac{3^k-1}{2}=1,4,13,40,121,\ldots

较大gap迅速减少长距离逆序，使后续较小gap面对partially sorted input。前一次h-sorted经过下一次gap insertion后，不必保留旧h-sorted，但最终gap 1建立全局顺序。官方2.1给出的性质是比较次数受N乘gap数量的小常数倍控制，并给出该increment sequence的上界：

C_{\mathrm{shell}}(N)=O\!\left(N^{3/2}\right)

这个bound不表示每个input都恰好N的3/2次方，也不说明Shellsort稳定。Gap大于1时相等keys可跨过彼此，因此通常不稳定。它原地、代码短，在中等规模实践中可用，但其性能高度依赖increment sequence；不能把某个sequence的结论外推给所有gap设计。

2.1.6 Cost experiment：让算法与输入模型一起被比较

SortCompare 对每个trial生成相同长度的random array，分别调用命名sort并累计wall time。公平实验应让两个算法获得相同input copies，排除生成和I/O时间，先warm up JVM，并报告多次分布而非只给一个ratio。Random doubles只代表一种input model，不代表近乎有序、重复key多或交换昂贵的业务数据。

选择排序的比较数只由N决定；插入排序还由I决定；Shellsort还由gap sequence与各gap后的局部disorder决定。Operation counter可验证数学模型，wall clock用于评估实现常数，两者角色不同。若计时结果与operation counts矛盾，应先检查JIT、GC、cache、allocation和复制边界，而不是直接否定推导。

可靠的property test应覆盖empty、single item、already sorted、reverse、all equal、duplicate labels、random、organ-pipe以及adversarial comparator。结果与标准库sort或独立stable oracle比对，同时验证permutation、sortedness、稳定性声明、extra allocation和operation counts。

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“2.1 · Elementary Sorts”的两个最小情境间切换，再逐项选择正式概念。预测“选择排序比较约 N^2/2 次；插入排序交换数等于输入逆序对数”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

2.1 · Elementary Sorts：对象、操作与不变量

用选择、插入和希尔排序的交换轨迹解释局部有序度、成本与适用输入

选择最小情境

切换正式概念

近乎有序: [1, 2, 4, 3, 5] 上比较选择排序与插入排序
当前观察: elementary sorts：插入排序只修复少量逆序，选择排序仍完成固定数量比较

选择排序比较约 N^2/2 次；插入排序交换数等于输入逆序对数

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

初级排序：在实验 1 中指出对应状态，并写出一个通过条件。
选择排序：在实验 2 中指出对应状态，并写出一个通过条件。
插入排序：在实验 3 中指出对应状态，并写出一个通过条件。
排序可视化：在实验 1 中指出对应状态，并写出一个通过条件。
希尔排序：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“选择排序比较约 N^2/2 次；插入排序交换数等于输入逆序对数”不是孤立结论？

选择“近乎有序”的输入：[1, 2, 4, 3, 5] 上比较选择排序与插入排序。按选择算法与 h → 定位局部逆序 → 移动或交换元素 → 扩大有序区域 → 核对全序和多重集保存状态，并用“插入排序只修复少量逆序，选择排序仍完成固定数量比较”核对方向；随后只改变一个变量，检查公式的前提和边界是否仍成立。

问题 3：故障恢复。 怎样证明“插入时把比较边界写成 j > 0 却读取 a[j-1] 之外的位置，或遗漏最后一个 h=1”已经修复？

保存原数组、h 序列、比较/交换计数、每轮数组快照、稳定性标签与排序预言机作为正常基线；注入该故障并标记第一个违反“每轮结束后声明的前缀、后缀或 h-子序列必须有序，元素多重集保持不变”的状态；撤销后用完全相同的输入、版本和随机种子重放。只有全部状态与独立预言机重新一致，才可发布修复结论。

本章回顾

Elementary sorts共享total order、sorted permutation、space与stability契约。
Selection sort每轮选择剩余minimum，固定做N平方除2次比较与线性交换。
Insertion sort维护有序前缀，交换次数恰等于input inversions，部分有序时接近线性。
Sorting visualization揭示移动模式，但正确性仍依赖prefix、permutation与order invariants。
Stability必须用带identity的equal keys检查；官方插入排序稳定，选择排序与Shellsort通常不稳定。
Shellsort通过递减gaps建立h-sorted subsequences，最终gap 1完成全局排序。
SortCompare式实验必须固定input model与测量边界，并与operation-count模型交叉验证。