主题
字号
CHAPTER 05 ≈ 48 MIN READ

查找与排序

5.1 查找的基本概念与 ASL

5.1.1 一组术语

查找（搜索） 就是在一堆数据里，找出「关键字」等于某个给定值的那个记录。几个术语必须分清：

5.1.2 ASL——衡量查找快慢的核心指标

衡量一个查找算法好不好，核心指标是 ASL（Average Search Length，平均查找长度）——平均要做多少次「关键字比较」才能找到（或确定找不到）一个元素。注意单位是「比较次数」，不是时间秒数，这样和机器无关，纯粹反映算法本身。ASL 越小越快。这是这一章贯穿始终、必考必算的量。

ASL = Σ (Pᵢ × Cᵢ)     （i 从 1 到 n）
其中 Pᵢ 是查找第 i 个元素的概率，Cᵢ 是找到它所需的比较次数。
通常假设每个元素被查的概率相等，即 Pᵢ = 1/n，于是 ASL = (1/n)·Σ Cᵢ。

ASL 必须分两种情况，考试常分开问，务必都会算：

为什么要分开？因为「找到」和「确认找不到」的代价往往不同。比如顺序查找一个不存在的元素，必须把整张表比完才能下结论，代价比平均找到一个存在的元素更大。

5.2 顺序查找（线性查找）

5.2.1 思想与代码

最朴素的方法：从头到尾一个个比，直到找到或走完。对存储、对数据是否有序都没有要求（无序也行，链式也行），这是它最大的优点。

// 在数组 a[0..n-1] 中顺序查找 key，返回下标，找不到返回 -1
int SeqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;     // 逐个比较
    return -1;                          // 走完没找到
}

5.2.2 哨兵优化

上面循环每次都要判断两件事：i < n（没越界）和 a[i] == key（是不是目标）。可以用「哨兵」省掉边界判断：把要找的 key 先放到数组的 0 号位置（或 n 号位置）当哨兵，然后从另一端往回找。这样循环一定会在碰到目标或哨兵时停下，不需要每次判断越界，比较次数省了近一半。教材常用这种带哨兵的版本：

// 哨兵版：a[0] 当哨兵位，实际数据存在 a[1..n]
int SeqSearchGuard(int a[], int n, int key) {
    a[0] = key;                 // 在 0 号位放哨兵
    int i = n;
    while (a[i] != key) i--;     // 从后往前找，不用判越界——最差也会停在 a[0]=key
    return i;                    // 返回 0 表示没找到（停在了哨兵处），否则返回下标
}

5.2.3 ASL 分析（必考）

假设每个元素等概率被查（Pᵢ = 1/n）。在上面正向版本里，找第 1 个比 1 次，第 2 个比 2 次……第 n 个比 n 次：

查找成功 ASL = (1 + 2 + ... + n) / n = (n+1)/2 ≈ O(n)
查找不成功 ASL = n+1（带哨兵）或 n（不带），都要把全表比完才能确定 → O(n)

如果各元素的查找概率不等，则应把查找概率大的元素放在表的前面，能减小 ASL（常用的先排到前面，少用的放后面），这是一个常考的优化结论。

优点：简单，对数据无任何要求（无序、链式都行）。缺点：慢，O(n)。适用：数据量小、或无序又不值得专门排序时。

5.3 折半查找（二分查找，必考）

5.3.1 大前提与思想

两个大前提，缺一不可：表必须① 顺序存储（数组）② 已经有序！ 二分的全部威力都建立在「有序」上，无序绝对不能用，链表也不能用（链表无法 O(1) 跳到中间）。

思想：每次和正中间那个元素比。如果 key 比中间的小，那它只可能在左半边（右半边连同中间都排除）；比中间大就在右半边；相等就找到了。每比一次就砍掉一半的范围，所以极快。这正是前面说的「不断对半 → O(log n)」。

// 在有序数组 a[0..n-1] 中二分查找 key，返回下标，找不到返回 -1
int BinarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {                    // 注意是 <= ，区间 [low, high] 含两端
        int mid = (low + high) / 2;          // 取中间（整除，相当于向下取整）
        if (a[mid] == key) return mid;       // 命中
        else if (key < a[mid]) high = mid - 1;   // key 在左半边，砍掉右边（含 mid）
        else                   low  = mid + 1;   // key 在右半边，砍掉左边（含 mid）
    }
    return -1;                               // low > high，区间空了，没找到
}

两个易错点：① 循环条件是 low <= high（区间含两端，相等时还有一个元素要查，不能漏）；② 更新边界是 mid-1 / mid+1（mid 已经比过了，要排除掉，否则可能死循环）。

复杂度：每次范围减半，最多比 ⌊log₂n⌋+1 次，O(log n)。比顺序查找快一个数量级（n=1000 时，顺序平均比 500 次，二分最多 10 次）。

5.3.2 判定树（必考工具）

二分查找的整个比较过程，可以画成一棵二叉判定树：根是第一次比的中间元素，它的左孩子是「左半区的中间元素」、右孩子是「右半区的中间元素」，递归下去，直到每个区间只剩一个或空。这棵树的形状和二分过程一一对应——在判定树里找到某个节点要比较的次数 = 它所在的层数（根是第 1 层）。

判定树有几个重要性质：

5.3.3 ASL 完整计算示例（务必练熟）

画判定树算 ASL 是必考的机械送分题。以 n = 11（下标 1~11 的有序表）为例，构造判定树并算两种 ASL。

每次取 mid = ⌊(low+high)/2⌋。区间 [1,11] → mid=6（根，第1层）。

各节点所在层数（=比较次数）统计：

查找成功 ASL = (1×1 + 2×2 + 3×4 + 4×4) / 11 = (1 + 4 + 12 + 16) / 11 = 33/11 = 3。

查找不成功 ASL：在判定树每个空指针处补上「方形外部节点」（落到这里就是查找失败），n=11 有 12 个外部节点（n+1 个失败区间）。某个外部节点的比较次数 = 它所在层数 − 1（=它父内部节点的层数）。本例外部节点分布：

查找不成功 ASL = (3×4 + 4×8) / 12 = (12 + 32) / 12 = 44/12 = 11/3 ≈ 3.67。

考点固定：给 n 或一个有序表，画出判定树并算成功/不成功的 ASL。务必动手画几个不同 n（如 7、10、11、13）练熟。注意：折半判定树的形状唯一（mid 取法固定），所以 ASL 是确定值；而 BST 的形状依赖插入顺序，同样的数不同插入顺序 ASL 不同——这点常被拿来对比出判断题。

5.4 分块查找（索引顺序查找，折中方案）

5.4.1 思想

介于顺序和二分之间的折中。把数据分成若干块，要求块间有序（前一块的所有元素都小于后一块的所有元素，即「块间递增」），但块内可以无序。再建一张索引表，每一项记录一块的最大关键字和该块的起始位置。

查找分两步：① 先在索引表里确定 key 落在哪一块（索引表是有序的，可用顺序查找或二分查找）；② 再在那一块里顺序查找。

5.4.2 ASL 与最佳分块

设总共 n 个元素，均分成 b 块，每块 s 个（n = b×s）。

ASL = L_索引（查索引表确定块）+ L_块内（在块里顺序找）
若两步都用顺序查找：ASL ≈ (b+1)/2 + (s+1)/2

用均值不等式可证：当 s = √n（每块大小取 √n、共 √n 块）时，ASL 取最小值约 √n + 1。所以分块查找的效率介于顺序 O(n) 和二分 O(log n) 之间，约 O(√n)。

优点：插入删除比二分灵活（只动一块，不用整体保持严格有序）。适用：数据量大、又需要兼顾查找和频繁插删的场景。

5.5 树表查找（归纳，详见第3章）

这部分在第3章（树）已详细讲过，这里从「查找视角」归纳，需要复习就回看第3章树表相关小节：

它们都属于动态查找（边查边能高效增删），查找效率和「树高」直接挂钩。

5.6 哈希表（散列，必考重点，加厚）

5.6.1 革命性思想：不比较，直接算地址

前面所有查找——顺序、二分、树——本质都是「通过比较关键字来缩小范围」，再快也得 O(log n)。哈希表换了一个全新思路：不比较，直接用关键字「算」出它该待的位置。

具体说，设计一个哈希函数（散列函数）H，输入关键字 key，输出一个数组下标 H(key)。存的时候把 key 放到 H(key) 这个位置；查的时候再用同一个 H 算出 H(key)，直接到那个位置去拿——一步到位，不用比较，平均 O(1)！ 这是哈希表惊人速度的来源，是「用空间换时间」的极致。

类比：图书馆规定「书名拼音首字母 A 的全放 1 号架、B 放 2 号架……」，找书时按首字母直接走到对应架子，不用一本本翻。哈希函数就是这个「按规律算位置」的规则。

5.6.2 哈希函数的构造方法

好的哈希函数要让不同 key 尽量均匀地散布、少「撞车」，且计算简单。常见方法：

考试基本只用除留余数法，记死「H(key)=key%p，p 取不超过表长的最大质数」。

5.6.3 冲突及其处理（核心考点）

冲突（碰撞）：不同的 key 算出了相同的地址（H(k1)==H(k2)）。这几乎不可避免（key 多、位置有限，鸽巢原理）。两大类处理方法：

方法一：开放定址法（冲突了就另找空位）

发生冲突时，按某种规则探测下一个位置，直到找到空位。通用公式 Hᵢ = (H(key) + dᵢ) % m（m 是表长，dᵢ 是增量序列）：

方法二：链地址法（拉链法，最常用）

思想：算出同一个地址的所有元素，用一个链表串在这个地址下面。哈希表的每个槽位存一个链表头，冲突的元素就往对应链表上挂（通常头插）。查找时算出地址、再在那条（通常很短的）链表里顺序找。

优点：实现简单；不会因为表「满」而无处可放（链表能一直挂）；删除方便（链表删节点，不像开放定址删除会破坏探测链）；没有堆积问题。这是实际工程最常用的方法（Java HashMap、各种语言字典底层都是拉链或其变体）。

5.6.4 装填因子与 ASL 的关系

装填因子 α = 表中已有元素个数 n / 哈希表长度 m。 它衡量表的「拥挤程度」。α 越大（越满），冲突越多、查找越慢；α 越小越快但越浪费空间。这又是「时间 vs 空间」的权衡，一般控制 α 在 0.7~0.8。

关键结论（必考）：哈希表的 ASL 只和装填因子 α 有关，和元素总数 n 本身无关。 这是哈希表能维持 O(1) 的根本——只要控制好 α，不管表里有 100 个还是 100 万个元素，平均查找时间都差不多。理论上的近似公式（了解）：

5.6.5 ASL 计算——线性探测完整示例

经典题型：「给定一组 key、表长、哈希函数、冲突处理方法，画出哈希表，计算成功/不成功 ASL。」这是哈希章节的头号送分大题，必须练到稳。

例 1（线性探测）：关键字 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，表长 m=13，H(key)=key%13，线性探测。

先算各 key 的哈希地址（key % 13）：

key 19 14 23 1 68 20 84 27 55 11 10 79
H 6 1 10 1 3 7 6 1 3 11 10 1

依次放入，冲突就线性往后探测（每探测一个位置记 1 次比较）：

key 起始地址 实际落位（探测过程） 比较次数
19 6 6 空，放 1
14 1 1 空，放 1
23 10 10 空，放 1
1 1 1被占→2空，放 2
68 3 3 空，放 1
20 7 7 空，放 1
84 6 6占→7占→8空，放 3
27 1 1占→2占→3占→4空，放 4
55 3 3占→4占→5空，放 3
11 11 11 空，放 1
10 10 10占→11占→12空，放 3
79 1 1→2→3→4→5→6→7→8→9空，放 9

最终表（下标0~12）：[_, 14, 1, 68, 27, 55, 19, 20, 84, 79, 23, 11, 10]。

查找成功 ASL = (1+1+1+2+1+1+3+4+3+1+3+9) / 12 = 30 / 12 = 2.5。

查找不成功 ASL：注意——不成功是按哈希函数的值域算（这里 H 值是 key%13，值域 0~12，共 13 个可能的起始地址）。对每个起始地址，数「从这里开始线性探测，一直比到碰见第一个空位为止」的比较次数（碰到空位本身也算 1 次比较来确认它空）。

照最终表逐个数（地址0是空的）：

把 13 个地址的比较次数平均即为不成功 ASL。（这一步要照最终表仔细数，本例因为表几乎填满，不成功 ASL 偏大。考试给的表通常没这么满，照样按「从该地址数到第一个空位」的规则数即可。）

数不成功 ASL 的口诀：对每个哈希地址（按 H 值域 0~p−1），从该地址往后数，直到遇到第一个空位为止的格子数（含那个空位），就是从这个地址查找失败的比较次数；把所有地址的次数求平均。

5.6.6 ASL 计算——拉链法完整示例

例 2（拉链法）：同样的 key {19,14,23,1,68,20,84,27,55,11,10,79}，H(key)=key%13，拉链法（每个地址挂一条链表，新元素头插或尾插，这里按尾插，链上比较次数从1开始数）。

按地址归类（key%13）：

查找成功 ASL = 所有元素比较次数之和 / 元素个数 = [ (1+2+3+4) + (1+2) + (1+2) + 1 + (1+2) + 1 ] / 12 = [ 10 + 3 + 3 + 1 + 3 + 1 ] / 12 = 21 / 12 = 1.75。

查找不成功 ASL：对每个哈希地址（0~12，共13个），不成功的比较次数 = 该地址链表上的节点个数（要把整条链比完才能确定不在；空链算 0 次比较，有的教材算遇到空链就是0）。 各地址链长：地址1长4、地址3长2、地址6长2、地址7长1、地址10长2、地址11长1，其余9个地址长0。

不成功 ASL = (4+2+2+1+2+1+0×7) / 13 = 12 / 13 ≈ 0.92。

对比线性探测，拉链法的 ASL 明显更小（成功 1.75 vs 2.5），因为没有堆积。这印证了拉链法的优势。两种方法各算一遍，体会差别。

5.6.7 开放定址法的删除问题（易忽略的考点）

开放定址法不能简单地把要删的元素位置直接清空！因为查找是靠「探测链」一路找下去的，如果中途清空了一个位置，会让探测链「断掉」，后面本来能找到的元素就找不到了。正确做法是给被删位置打一个「已删除」的标记（懒删除），查找时遇到标记继续往后探测、插入时可以覆盖标记位。这是开放定址法相比拉链法的又一个麻烦（拉链法删除就是链表删节点，干净利落）。

5.6.8 哈希表小结

5.7 各查找方法对比（汇总）

方法 前提 平均时间 是否支持动态增删 特点
顺序查找 无 O(n) 是 简单，对数据无要求
二分查找 有序+顺序存储 O(log n) 否（增删要保序，代价高） 快但静态
分块查找 块间有序 O(√n) 较灵活 兼顾查找与增删
BST 树结构 O(log n)，最坏 O(n) 是 可能退化
AVL 平衡树 O(log n) 是 防退化，旋转维护
哈希表 哈希函数 O(1) 是 最快，但无序、费空间

5.8 查找自测

  1. 什么是 ASL？为什么要分「成功」和「不成功」两种？
  2. 顺序查找成功 ASL 是多少？查找概率不等时如何优化？哨兵的作用？
  3. 二分查找的两个前提？复杂度？循环条件为什么是 low<=high？
  4. 画出 n=10 的二分判定树，算成功与不成功 ASL。
  5. 分块查找「块间有序、块内无序」是什么意思？最佳块大小是多少，对应 ASL？
  6. 哈希表的核心思想（和前面所有查找的本质区别）？
  7. 除留余数法的 p 怎么取？为什么取质数？
  8. 线性探测的堆积是什么？拉链法相比有哪些优势？
  9. 装填因子是什么？哈希 ASL 和 n 有关还是和 α 有关？
  10. 自己出一组 key，分别用线性探测和拉链法（H=key%7），画表并算成功+不成功 ASL，对比两者。
  11. 开放定址法删除元素为什么不能直接清空？怎么办？

排序是分值最高的一章，几乎必出大题，考点很「死」（对比表、一趟/多趟模拟），属于只要练到位就能拿满分的章节，务必重视并多动手模拟。

5.9 排序的基本概念

排序：把一组记录按关键字的大小，重新排成递增（或递减）顺序。关键概念贯穿全章：

下面按「类别」讲，每个算法都讲清 思想 + 完整多趟模拟 + 复杂度 + 稳定性。统一以待排数组 49 38 65 97 76 13 27（7 个数）做模拟，方便对比。

5.10 插入排序类

5.10.1 直接插入排序

思想：像理扑克牌。把数组分成「前面已排好的有序区」和「后面待排区」。每次从待排区取第一个元素，从后往前在有序区里找到它该插的位置插进去（沿途比它大的元素都往后挪一格腾位置）。有序区从只含第 1 个元素开始，逐步扩大到整个数组。

void InsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) {        // a[0] 看作已排好，从 a[1] 开始往里插
        if (a[i] >= a[i-1]) continue;    // 小优化：已经≥前一个就不用插
        int temp = a[i];                 // 暂存待插元素（它的位置要被覆盖）
        int j = i - 1;
        while (j >= 0 && a[j] > temp) {   // 从后往前：比 temp 大的都往后挪
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;                 // 找到位置，插入
    }
}

完整多趟模拟（49 38 65 97 76 13 27，方括号是有序区）：

初始:    [49] 38  65  97  76  13  27
插38:    [38  49] 65  97  76  13  27      （38<49，49后移）
插65:    [38  49  65] 97  76  13  27      （65>49，原位）
插97:    [38  49  65  97] 76  13  27      （97最大，原位）
插76:    [38  49  65  76  97] 13  27      （76插到65和97之间）
插13:    [13  38  49  65  76  97] 27      （13最小，插到最前）
插27:    [13  27  38  49  65  76  97]     （27插到13和38之间）完成

复杂度：最好（已有序）每个只比 1 次、不挪，O(n)；最坏（逆序）第 i 个要挪 i 次，总 O(n²)；平均 O(n²)。空间 O(1)。稳定（a[j] > temp 才挪，相等不挪，相等元素不会越过彼此）。

5.10.2 折半插入排序

直接插入里「在有序区找插入位置」用的是顺序比较。既然有序区已经有序，找位置可以用二分！这就是折半插入——用折半查找确定插入位置，把比较次数从 O(n) 降到 O(log n)。但移动元素的次数没变（找到位置后照样要挪后面的元素腾位）。所以时间复杂度仍是 O(n²)（瓶颈在移动），只是比较次数降到 O(n log n)。空间 O(1)，稳定。

考点辨析：折半插入相比直接插入，减少的是比较次数，不是移动次数，总时间仍 O(n²)。这个细节常考。

5.10.3 希尔排序（缩小增量排序）

思想：直接插入在「基本有序」时很快（接近 O(n)），但在「乱序」时慢，且每次只能挪一格、效率低。希尔的巧思：先让数组变得「基本有序」，再做插入排序，并且让元素能大步跨越式移动。

具体：取一个增量 gap（如 n/2），把相隔 gap 的元素分成一组，对每组分别做直接插入排序（这是一趟）；然后缩小 gap（如再减半）再来一趟；直到 gap=1（此时就是对整个已基本有序的数组做一次普通插入排序，很快）。大增量时元素能「跳跃式」大步移动到大致位置，避免了一格格挪。

完整模拟（49 38 65 97 76 13 27，n=7，增量取 gap=3,1）：

gap=3: 分3组（下标0,3,6 | 1,4 | 2,5）
       组1: 49,97,27 → 排序 → 27,49,97
       组2: 38,76    → 38,76（不变）
       组3: 65,13    → 13,65
       结果: 27  38  13  49  76  65  97
gap=1: 对 27 38 13 49 76 65 97 做普通插入排序
       → 13  27  38  49  65  76  97  完成

复杂度：和增量序列选取有关，平均约 O(n^1.3)（希尔增量），最坏 O(n²)，比纯 O(n²) 好。空间 O(1)。不稳定（相等元素可能被分到不同组，相对位置被打乱）。

希尔是第一个突破 O(n²) 的排序。记住：分组靠增量、增量逐渐缩到 1、不稳定。

5.11 交换排序类

5.11.1 冒泡排序

思想：相邻两元素比较，前者比后者大就交换。一趟从头扫到尾，最大的元素像气泡「冒」到最后。下趟范围缩小（末尾已归位），重复，直到某趟没有发生交换（已有序，可提前结束）。

void BubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {            // 最多 n-1 趟
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {     // 每趟把当前最大冒到末尾，范围递减
            if (a[j] > a[j + 1]) {                // 相邻逆序就交换
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;                      // 一趟没交换=已有序，提前结束
    }
}

完整多趟模拟（49 38 65 97 76 13 27，每趟后最大值归位，下划线表示已归位区）：

初始:  49 38 65 97 76 13 27
第1趟: 38 49 65 76 13 27 |97     （97冒到末尾）
第2趟: 38 49 65 13 27 |76 97     （76归位）
第3趟: 38 49 13 27 |65 76 97
第4趟: 38 13 27 |49 65 76 97
第5趟: 13 27 |38 49 65 76 97
第6趟: 13 |27 38 49 65 76 97     （此趟无交换或仅一次，已有序）完成

复杂度：最好（已有序，有 swapped 优化）一趟发现无交换，O(n)；最坏（逆序）O(n²)；平均 O(n²)。空间 O(1)。稳定（a[j] > a[j+1] 才换，相等不换）。

一趟特征（考点）：冒泡一趟后，当前最大值一定归位到末尾（若从后往前冒则最小值归位到开头）。

5.11.2 快速排序（重点中的重点）

思想（分治）：选一个元素作基准（pivot），通过一趟划分（partition）把比基准小的甩到左边、比它大的甩到右边——基准就落到了它最终的位置。然后对左右两部分递归地快排。分而治之。

// 一趟划分：以 a[low] 为基准，小的放左、大的放右，返回基准最终位置
int Partition(int a[], int low, int high) {
    int pivot = a[low];                          // 选第一个作基准（暂存，low 位空出）
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;  // 右指针左移，找比基准小的
        a[low] = a[high];                        // 填到左边空位
        while (low < high && a[low] <= pivot) low++;    // 左指针右移，找比基准大的
        a[high] = a[low];                        // 填到右边空位
    }
    a[low] = pivot;                              // low==high，基准归位
    return low;
}
void QuickSort(int a[], int low, int high) {
    if (low < high) {
        int pos = Partition(a, low, high);       // 划分，基准归位
        QuickSort(a, low, pos - 1);              // 递归排左半
        QuickSort(a, pos + 1, high);             // 递归排右半
    }
}

一趟 partition 完整模拟（49 38 65 97 76 13 27，pivot=49，low/high 双指针）：

初始: 49 38 65 97 76 13 27   pivot=49，low=0 high=6
右找<49: 27(下标6) → 填到low: 27 38 65 97 76 13 _      low=0,high=6→...
左找>49: 65(下标2) → 填到high: 27 38 _ 97 76 13 65     low=2
右找<49: 13(下标5) → 填到low: 27 38 13 97 76 _ 65      high=5
左找>49: 97(下标3) → 填到high: 27 38 13 _ 76 97 65     low=3
右找<49: 无(high移到low) → low==high==3
基准归位: 27 38 13 [49] 76 97 65

一趟后 49 归位，左边 27 38 13 全 <49，右边 76 97 65 全 >49。再对左右递归。

递归全过程（简示）：

[49 38 65 97 76 13 27]
 → 27 38 13 [49] 76 97 65
   左[27 38 13] → 13 [27] 38（27归位）→ ... → 13 27 38
   右[76 97 65] → 65 [76] 97（76归位）→ 65 76 97
 → 13 27 38 49 65 76 97  完成

复杂度：平均 O(n log n)（每次大致均分，log n 层、每层 partition 共 O(n)），是平均最快的排序（常数因子小，实际跑得最快）。最坏 O(n²)：当每次划分极不均匀——典型是数组已经有序（或逆序）且总取端点作基准，每次只分出一个元素，退化成 O(n²)。空间 O(log n)（递归栈深度，平均；最坏 O(n)）。不稳定。

快排考点：① 一趟 partition 结果（必考手动模拟）；② 最坏 O(n²) 何时发生、怎么避免（随机基准 / 三数取中）；③ 平均 O(n log n)、不稳定、空间 O(log n)。

5.12 选择排序类

5.12.1 简单选择排序

思想：每趟从未排序区里挑出最小元素，放到已排序区末尾（和未排序区第一个交换）。第 1 趟选全局最小放第 1 位，第 2 趟选剩下最小放第 2 位……

void SelectSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;                          // 假设未排序区第一个最小
        for (int j = i + 1; j < n; j++)       // 在剩下的里找真正最小的
            if (a[j] < a[min]) min = j;
        if (min != i) {                        // 把最小的换到位置 i
            int t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }
}

完整模拟（49 38 65 97 76 13 27，竖线左为已排序区）：

初始:  49 38 65 97 76 13 27   选最小13，与49换
第1趟: 13 |38 65 97 76 49 27   选最小27，与38换
第2趟: 13 27 |65 97 76 49 38   选最小38
第3趟: 13 27 38 |97 76 49 65   选最小49
第4趟: 13 27 38 49 |76 97 65   选最小65
第5趟: 13 27 38 49 65 |97 76   选最小76
第6趟: 13 27 38 49 65 76 |97   完成

复杂度：不管数据啥样都要全扫描比较，最好/平均/最坏都是 O(n²)（比较次数固定 n(n−1)/2，与输入无关）。空间 O(1)。不稳定（交换可能打乱相等元素顺序，如 5ₐ 5ᵦ 2，第一趟把 2 和 5ₐ 交换，两个 5 顺序就反了）。

特点：移动次数极少（每趟最多 1 次交换），但比较次数固定且多。

5.12.2 堆排序（重点）

第3章讲过堆，这里讲它怎么排序。思想：① 把数组建成大顶堆（堆顶=最大值）；② 把堆顶（最大值）和数组最后一个元素交换——最大值落到最终位置；③ 堆范围缩小 1，对新堆顶做一次下沉恢复大顶堆；④ 重复②③，每次「沉淀」一个最大值到后面，直到全部有序。

// 下沉：把 a[i] 在范围 [0,n) 内向下调整，维持大顶堆（下标从0开始：左孩2i+1，右孩2i+2）
void SiftDown(int a[], int i, int n) {
    int temp = a[i];
    for (int child = 2*i+1; child < n; child = 2*child+1) {
        if (child+1 < n && a[child+1] > a[child]) child++;   // 取较大的孩子
        if (a[child] <= temp) break;                          // 已满足堆序，停
        a[i] = a[child]; i = child;                           // 大孩子上移，继续下沉
    }
    a[i] = temp;
}
void HeapSort(int a[], int n) {
    for (int i = n/2 - 1; i >= 0; i--) SiftDown(a, i, n);     // 1.建大顶堆
    for (int i = n - 1; i > 0; i--) {                         // 2.反复换堆顶到末尾+下沉
        int t = a[0]; a[0] = a[i]; a[i] = t;
        SiftDown(a, 0, i);
    }
}

建堆过程模拟（49 38 65 97 76 13 27，对应完全二叉树，从最后一个非叶节点 i=2 开始下沉）：

初始树:        49
            /     \
          38       65
         /  \      /  \
        97  76    13  27
下沉i=2(65): 65的孩子13,27都小，不动
下沉i=1(38): 孩子97,76，97最大>38 → 换 → 38和97换位
下沉i=0(49): 孩子97(已上来),65 → 97最大>49 → 49与97换 → 49下沉到原97位，
            49再和它的孩子76比 → 76>49 → 换
建堆结果(大顶堆): 97 76 65 38 49 13 27   （堆顶97是最大值）

排序阶段：把堆顶 97 和末尾 27 交换→97归位→对前6个下沉恢复堆→再换堆顶到倒数第二位……每趟沉淀一个最大值。

复杂度：建堆 O(n)（反直觉但可证，底层大量节点下沉代价小），之后 n−1 次下沉每次 O(log n)，整体 O(n log n)，且最好/平均/最坏都是 O(n log n)（性能稳定，无退化）。空间 O(1)（原地）。不稳定。

堆排独特优势：O(n log n) 且原地 O(1) 空间——归并是 nlogn 但要 O(n) 空间，快排 nlogn 但最坏退化。空间紧张又要保证 nlogn时选堆排。考点：建堆过程、一趟（堆顶换末尾+下沉）后的序列。

5.13 归并排序

思想（分治）：把数组对半分成两半，分别递归排好，再把两个有序半边合并（merge）成完整有序数组。「分」到每段剩一个元素（天然有序），再一层层「合并」回去。核心子操作是合并两个有序序列：双指针各扫一段，每次取较小的放进结果。

void Merge(int a[], int low, int mid, int high) {
    int *temp = (int*)malloc((high-low+1)*sizeof(int));   // 辅助数组（O(n)空间来源）
    int i = low, j = mid+1, k = 0;
    while (i <= mid && j <= high)
        temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];      // <= 保证稳定：相等取左边
    while (i <= mid)  temp[k++] = a[i++];                  // 左段剩余接上
    while (j <= high) temp[k++] = a[j++];                  // 右段剩余接上
    for (k = 0, i = low; i <= high; i++) a[i] = temp[k++]; // 拷回
    free(temp);
}
void MergeSort(int a[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);
        Merge(a, low, mid, high);
    }
}

完整分治模拟（49 38 65 97 76 13 27）：

分解（一直对半分到单个）:
[49 38 65 97 76 13 27]
[49 38 65 97] [76 13 27]
[49 38][65 97] [76][13 27]
[49][38][65][97] [76][13][27]
合并（两两有序合并往上）:
[38 49][65 97] [76][13 27]
[38 49 65 97]  [13 27 76]
[13 27 38 49 65 76 97]  完成

复杂度：分 log n 层、每层合并共 O(n)，最好/平均/最坏都是 O(n log n)（稳定的性能）。空间 O(n)（合并要辅助数组，最大缺点）。稳定（合并时相等取左边，保持相对顺序——a[i] <= a[j] 取左是稳定的关键）。

5.14 基数排序（分配排序类）

思想：不比较大小，而是按「位」分配和收集。以整数为例，从最低位（个位）开始：把所有数按个位数字分到 0~9 共 10 个「桶」（队列）里，再按桶顺序依次收集起来；然后按十位再分一遍、收集；再按百位……分配到最高位后，序列就有序了。这叫最低位优先（LSD）。

为什么能行：每轮按某一位分桶+收集是稳定的，低位先排、高位后排，高位相同的数会保持低位排好的相对顺序，逐位下来整体有序。

完整模拟（329 457 657 839 436 720 355，3位数，分两位太长，这里走个位+十位+百位）：

按个位分桶收集: 720 | 355 | 436 | 457 657 | 329 839   →  720 355 436 457 657 329 839
按十位分桶收集: 720 329 436 839 355 457 657            →  720 329 436 839 355 457 657
按百位分桶收集: 329 355 436 457 657 720 839            →  329 355 436 457 657 720 839 完成

复杂度：设 d=最大数位数、r=基数（十进制 r=10）、n=元素个数，则 O(d(n+r))。d 不大时接近线性，比 O(n log n) 还快。空间 O(r) 或 O(n+r)（桶开销）。稳定。

适用：关键字位数不多、范围有限的整数/定长字符串。考点：理解「按位分配-收集、低位优先、不比较」，知道它稳定、O(d(n+r))。

5.15 计数排序（非比较，了解）

思想：也不比较大小，而是统计每个值出现的次数。设元素取值在 0~k 范围内：① 开一个大小 k+1 的计数数组，扫一遍原数组数出每个值出现几次；② 求计数数组的前缀和（确定每个值在结果里的最终位置）；③ 从后往前把元素放到对应位置（从后往前是为了保持稳定）。

复杂度：时间 O(n+k)、空间 O(n+k)，稳定。适用：n 个元素但取值范围 k 不大（如分数 0~100）时，能做到接近线性、比 O(n log n) 还快；k 很大（值域稀疏）时浪费空间，不适合。基数排序内部每一趟分桶用的就是计数排序的思想。

5.16 排序算法总对比表（必背，直接考！）

排序章节的头号送分点，背到能默写：

排序算法 最好 平均 最坏 空间 稳定性
直接插入 O(n) O(n²) O(n²) O(1) 稳定
折半插入 O(n)（移动仍O(n²)） O(n²) O(n²) O(1) 稳定
希尔排序 — O(n^1.3) O(n²) O(1) 不稳定
冒泡排序 O(n) O(n²) O(n²) O(1) 稳定
快速排序 O(nlogn) O(nlogn) O(n²) O(logn) 不稳定
简单选择 O(n²) O(n²) O(n²) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定

5.16.1 记忆技巧（口诀+结论）

5.17 怎么选排序算法（考点逻辑）

5.18 外部排序（按大纲了解，常考概念）

前面都是内部排序（数据全在内存）。当数据量巨大、内存装不下（比如要排 100GB 的文件，内存只有 1GB）时，就需要外部排序——数据存在外存（磁盘），排序过程要在内存和磁盘间反复读写。外排序的瓶颈是磁盘 IO（远慢于 CPU 和内存），所以核心目标是减少 IO 次数。

5.18.1 基本流程：归并排序的思想

外排序通常基于归并，分两个阶段：

  1. 生成初始归并段（顺串）：把大文件分成若干段，每段小到能装进内存，在内存里用某种内排序（如快排）排好，写回磁盘。这些有序的段叫初始归并段（run）。
  2. 多路归并：把这些有序段两两（或 k 路）归并成更大的有序段，反复归并，直到合成一个完整有序的文件。

5.18.2 关键概念（考点）

外部排序考试一般考概念：为什么用归并、初始归并段怎么来、k 路归并减少趟数、败者树/置换选择/最佳归并树各解决什么问题。理解「减少 IO 是核心目标」这条主线即可。

5.19 排序大题的两类必考题型

  1. 「写出某趟排序后的序列」：给初始序列，问某算法第一趟（或第 k 趟）后数组变成什么样。每种算法的「一趟特征」要记牢：
    • 冒泡一趟：最大值冒到末尾（或最小值到开头）。
    • 快排一趟：基准归位，左小右大（partition 结果）。
    • 简单选择一趟：最小值放到最前。
    • 直接插入第 i 趟：前 i+1 个元素有序。
    • 堆排序：建堆后的序列、或一次「堆顶换末尾+下沉」后的序列。
    • 希尔一趟：按当前增量分组插入后的序列。
    • 归并一趟：相邻有序段两两合并后的序列。
  2. 默写对比表：时间/空间/稳定性（见 8.7）。

这两类题是排序章节的全部分数所在，手动模拟练熟 + 背熟对比表 = 满分。强烈建议刷题时给每种算法找一个初始序列，亲手把每趟都写出来对答案。

5.20 排序自测

  1. 什么是排序稳定性？举例说明它有什么用。
  2. 直接插入的思想？最好/最坏复杂度？为什么稳定？
  3. 折半插入相比直接插入，减少的是比较次数还是移动次数？总时间变了吗？
  4. 希尔排序的核心巧思？为什么不稳定？模拟 49 38 65 97 76 13 27 在 gap=3,1 下的过程。
  5. 冒泡一趟后什么元素一定归位？
  6. 写出 49 38 65 97 76 13 27 以首元素为基准的快排一趟划分结果。
  7. 快排平均/最坏复杂度？最坏何时发生？怎么避免？快排稳定吗？空间多少？
  8. 简单选择为什么最好情况也 O(n²)？它稳定吗？比较/移动次数特点？
  9. 堆排两大步骤？建堆复杂度？整体复杂度和空间？相比归并的独特优势？模拟一遍建堆。
  10. 归并为什么稳定？空间为什么 O(n)？
  11. 基数排序为什么不比较也能排？它稳定吗？复杂度？
  12. 默写排序对比表（9 种算法的最好/平均/最坏/空间/稳定性）。
  13. 外部排序为什么用归并？k 路归并为什么能减少 IO？败者树、最佳归并树各解决什么？