第2章 选择排序
从内存抽屉模型比较数组与链表，再完整推导选择排序的循环不变量、比较次数、交换次数和稳定性。
从一排内存抽屉开始
先预测：程序要保存五个整数。方案A把它们放进五个相邻抽屉；方案B把它们放到任意空抽屉，并在每个抽屉里留下“下一个在哪”的纸条。现在要读取第4个数、在第2个数后插入新值，哪种方案分别更省事？
第2章先讲内存怎样工作，再比较数组和链表，最后才引出选择排序。这个顺序很重要：算法写在某种数据结构上，性能不仅由“比较多少次”决定，还受元素怎样定位、移动和写回影响。
像一排带编号的抽屉。每个抽屉都有。数组利用连续地址直接计算第k项的位置；链表允许结点分散，再用链接串起逻辑顺序。
数组：连续内存与随机访问
使用连续内存。若首元素地址为 base，每个元素宽度为 w，下标为 i 的元素地址可直接计算：
因此是常数时间。这里的“随机”不是随机数，而是访问顺序不必从头向后走。数组读取第1项和第100万项都只需一次地址换算与一次读取，所以按下标读取是 O(1)。
代价出现在中间插入和删除。容量已满时，插入还可能先申请更大的连续区域；即使容量足够，也要把插入点之后的元素右移。删除中间元素后，为保持连续逻辑顺序，后缀通常左移填空。移动量最坏与 n 成正比，因此是 O(n)。
现代语言常用。它把扩容隐藏起来，并不改变“按下标读取快、中间移动贵”的核心性质。尾部追加在摊还意义上常为 O(1)，但某次扩容仍可能复制全部元素。
链表：分散结点与顺序访问
不要求元素相邻。每个包含值，还保存指向下一结点的。要读第k项，必须从头结点沿 next 走过前面各项；这叫，读取第k项最坏为 O(n)。
“链表插入删除是 O(1)”必须带条件：调用者已经持有插入位置的前驱结点，或已经持有待删结点及其前驱引用。此时只需改少数链接。若输入只是“在下标500处插入”或“删除值x”，寻找位置本身仍可能花 O(n)。把查找成本漏掉，会让接口层面的复杂度结论失真。
下面的函数把“已经持有前驱结点”写进参数，因此函数体只创建一个结点并改两条引用；从链表头寻找 previous 的过程不属于这个函数，却必须由调用方另行计入：
from dataclasses import dataclass
@dataclass
class Node:
value: int
next: "Node | None" = None
def insert_after(previous: Node, value: int) -> Node:
inserted = Node(value=value, next=previous.next)
previous.next = inserted
return inserted哪一种使用更多：数组还是链表
只看渐近表格，会误以为链表应在频繁插删时全面胜出；实际程序通常更常使用数组或动态数组。原因之一是：处理器从较慢内存取数时，往往把相邻的一小块一起带入缓存。数组连续遍历能利用这批数据，链表则可能每个结点都跳到远处，等待下一次取数。
数组还有更小的每元素元数据、更少的独立分配，以及成熟的索引和向量化支持。链表仍适合需要稳定结点地址、已知位置频繁拼接，或数据结构本身依赖链接的场景。结论不是“永远选数组”，而是把访问模式、修改位置、内存开销和实际硬件一起判断。
选择排序：每轮找出最小元素
把序列分成已排序区和。第 i 轮从下标 i 扫到末尾，只记录最小值的下标；扫描结束后，再把该值与下标 i 的元素交换。
以 [5, 3, 6, 2, 10] 为例：
- 扫描全部元素，最小值2在下标3，交换后得到
[2, 3, 6, 5, 10]。 - 从下标1扫描，最小值3已在边界，不必自交换。
- 从下标2扫描，找到5并与6交换，得到
[2, 3, 5, 6, 10]。 - 从下标3扫描，6已在正确位置；最后的10自然有序。
可以写成：第 i 轮开始时，前缀 values[0:i] 已有序，并且其中每个元素都不大于未排序区中的任何元素。扫描找到剩余最小值并放到位置 i 后，不变量对下一轮继续成立。最后未排序区只剩一个元素，整个数组有序。
from collections.abc import MutableSequence
from typing import TypeVar
T = TypeVar("T")
def selection_sort(values: MutableSequence[T]) -> None:
for boundary in range(len(values) - 1):
min_index = boundary
for index in range(boundary + 1, len(values)):
if values[index] < values[min_index]:
min_index = index
if min_index != boundary:
values[boundary], values[min_index] = (
values[min_index],
values[boundary],
)这个版本原地修改输入，不返回新列表。内层扫描期间不立即交换，只更新 min_index；这样每轮至多交换一次。若接口要求保留原输入，应先复制，或设计返回新序列的版本并把额外空间写进契约。
比较次数为何是平方级
第1轮需要比较 n-1 次，第2轮比较 n-2 次，直到最后一轮比较1次。总比较次数是：
因此选择排序的为 \Theta(n^2)，也常写作最坏 O(n²)。即使输入已经有序，普通选择排序仍要完成同样的扫描，因为不看完未排序区就无法证明当前项确实最小。
比较次数是平方级，不代表交换次数也是平方级。每轮至多交换一次，总共至多 n-1 次交换。对写入昂贵而比较便宜的小数据，这个性质有时有价值；但不能据此忽略 n(n-1)/2 次比较。
数组与链表上的选择排序
数组版本可用下标常数时间读取并交换，全部比较是 \Theta(n²)，额外空间是 O(1)。链表版本不应机械地写成 O(n³)：完全可以在每轮沿剩余结点顺序扫描，保存最小结点及其前驱，再改链接或交换值；所有轮次的扫描总量仍是 \Theta(n²)。
如果代码每次都调用“取第j个结点”并从头重走，确实可能制造额外成本，但那是特定低效实现，不是链表上选择排序的必然复杂度。实践中链表更常配合归并排序，因为归并能顺序访问并通过改链接完成合并，达到 O(n log n)；数组上的选择排序也通常只用于教学、极小输入或写次数受限的特殊情形。
稳定性与重复值
对多关键字排序很重要。普通交换版选择排序通常不稳定：输入 [2a, 2b, 1] 第一次把1与 2a 交换，得到 [1, 2b, 2a]，两个键值相等的2改变了相对顺序。
可以构造稳定变体：找出最小元素后先取出它，把边界到最小位置之间的元素整体右移一格，再把最小元素插到边界。这样保持相等元素顺序，却增加了移动次数。稳定性、比较数、写入数和额外空间是独立指标，不能只说“它是 O(n²)”就结束工程判断。
def test_selection_sort() -> None:
cases = [
[],
[7],
[5, 3, 6, 2, 10],
[1, 2, 3, 4],
[4, 3, 2, 1],
[3, 1, 3, 2, 1],
]
for values in cases:
expected = sorted(values)
selection_sort(values)
assert values == expected测试正确结果还不等于验证稳定性。要测试稳定排序，应让元素同时保存“排序键”和“原始身份”，排序后检查相等键的身份顺序。对本章的交换版，测试应明确记录它不承诺稳定，避免调用者建立错误依赖。
原章概念回查
内存像一排抽屉，每个位置有内存地址。数组使用连续内存；链表元素可分散存放并保存下一项地址。两者首先形成随机访问与顺序访问的区别：数组读取O(1)，链表读取O(n)。
数组中间插入需要移动后续元素；链表插入只需修改链接，但后一句以“目标位置及必要前驱已经找到”为条件。数组删除与链表删除的代价也必须拆成定位和修改两部分：数组删除常要移动后缀，链表删除在已持有前驱时只需绕过结点；若还要查找位置，完整操作会包含线性遍历。
现代程序更常使用数组或动态数组，缓存局部性让连续数组更快，也减少指针和独立分配开销。链表不是错误选择，而是用于更匹配链接操作与稳定结点地址的需求。
选择排序反复寻找最小元素。选择排序需要n次扫描的直觉更精确地说，是执行 n-1 轮有效选择，未排序区长度从n逐轮缩短；比较总数为 n(n-1)/2，因此可把结论记成“选择排序O(n²)”。它每轮至多交换一次，因此比较多而交换少。
本章回顾
- 数组连续存储，可由首地址和下标直接计算元素位置。
- 链表结点可分散，通过指针维护逻辑顺序。
- 数组随机访问是
O(1)，链表按位置读取是O(n)。 - 数组中间插删通常移动后缀，最坏为
O(n)。 - 链表改链接可为
O(1)，但寻找位置可能是O(n)。 - 连续数组通常比链表更能利用缓存局部性。
- 选择排序每轮从未排序区选出最小元素。
- 循环不变量说明已排序前缀有序且不大于剩余元素。
- 比较次数精确为
n(n-1)/2，量级为\Theta(n²)。 - 交换次数至多为
n-1，不能与比较次数混为一谈。 - 链表上的合理选择排序仍可为平方级，不是必然立方级。
- 普通交换版通常不稳定；稳定变体需要更多元素移动。