第八单元：选择排序 · 每轮择弱与队形整编

封神冰川的城门前，站着 8 名刚入伍、尚未受训的新兵，队伍杂乱无章。你的任务是把他们按身高从矮到高、从左到右排成一列。在游戏里，士兵的身高与他的 health（生命值）属性成正比——所以"按身高排序"其实就是"按血量排序"。要让程序自动完成这件事，你需要掌握一种经典而直观的排序算法：选择排序（selection sort）。

8.1.1 什么是排序（What Is Sorting）

8.1.1.1 把数据按大小排成有序 Arranging data in order

排序，就是把一组杂乱的数据按某种规则（从小到大、从高到矮…）重新排列成有序的一列。排序是计算机科学最基础也最常用的操作之一——有序的数据才能用上一单元的二分查找，才能快速找出最大最小、才能整齐地展示。本单元的目标数据就是 8 名士兵，排序依据是他们的 health。

8.1.2 选择排序的思想（The Idea of Selection Sort）

8.1.2.1 反复"选出最小、放到队尾" Repeatedly select the smallest and place it

选择排序的名字里"选择"二字就是关键：每一轮都在剩下的未排序数据里选出最小的一个，把它放到已排好队列的末尾。第一轮选出全场最矮的，放第 1 位；第二轮从剩下的里选最矮的，放第 2 位……如此往复，队列一个接一个地变长，直到所有人都被选完。

# 选择排序的通用骨架（以数字为例）
unsorted = [10, 12, 3, 1, 2, 6]
result = []
while len(unsorted):
    smallest = min(unsorted)   # 找最小
    result.append(smallest)      # 放到结果末尾
    unsorted.remove(smallest)   # 从未排序里移除

8.2.1 遍历求最小（Iterate to Find the Minimum）

8.2.1.1 打"反向擂台"找最弱者 A reverse tournament for the minimum

虽然 Python 有内置的 min()，但对一群士兵对象我们要按 health 比较，所以自己写一个求最小值的函数。方法是经典的求最小值算法：先设一个大得离谱的初始值 minHealth = 9001，遍历每个单位，谁的血量比当前记录更低，就更新记录并记住这个单位。遍历结束，记住的就是全场最弱者。

8.2.2 minHealthUnit 函数（The minHealthUnit Function）

8.2.2.1 补全关卡的求最弱者函数 Complete the weakest-unit function

关卡要求你补全 minHealthUnit(units)，它接收一个单位列表，返回其中 health 最低的那个。这就是上面求最小值算法的实现——它是整个排序的"引擎"，每一轮都靠它挑出下一个该归位的士兵。

# 返回列表中 health 最低（最矮）的单位
def minHealthUnit(units):
    weakest = None
    minHealth = 9001          # 故意设很大，方便被刷新
    for unit in units:
        if unit.health < minHealth:
            minHealth = unit.health
            weakest = unit    # 记住当前最弱者
    return weakest

8.3.1 markPos 与索引（Mark Positions by Index）

8.3.1.1 用序号算出每个标记的坐标 Compute each mark's position from its index

队形里有一排标记（mark），第 0 个、第 1 个…依次向右排开。关卡提供了 markPos(i) 函数：给它一个序号 i，它返回第 i 个标记的坐标——本质是 x = 12 + i*8, y = 12，即每往右一位 x 加 8。我们用一个计数器 markIndex 记录"下一个该填的位置"，从 0 开始。

# 关卡提供：返回第 i 个标记的坐标
def markPos(i):
    return {"x": 12 + i * 8, "y": 12}

markIndex = 0   # 下一个要填的位置序号

8.3.2 command 归位（Command the Unit into Place）

8.3.2.1 把最弱者送到当前标记 Send the weakest to the current mark

选出本轮最弱的士兵后，用 hero.command(weakestRecruit, "move", markPos(markIndex)) 命令他走到第 markIndex 个标记处。归位之后，把 markIndex 加 1，让下一轮的最弱者去填下一个位置。这样最矮的排最左、次矮的排其次……队形自然从矮到高。

# 找到最弱者，命令他去当前标记，再让序号前进
weakestRecruit = minHealthUnit(recruits)
hero.command(weakestRecruit, "move", markPos(markIndex))
markIndex += 1   # 下一位往右挪一格

8.4.1 重新查询名单（Re-query the Recruits）

8.4.1.1 归位的士兵会"自动消失" Placed soldiers drop out automatically

普通选择排序要手动 remove 已排好的元素，但这一关有个巧妙之处：findUnplacedSoldiers() 只返回还站在起点区、状态为 idle（发呆）的新兵。一旦你命令某个士兵移动，他就离开起点、不再 idle，下次查询名单时自动被排除。所以我们不需要手动移除，只要每轮重新调用 findUnplacedSoldiers() 刷新名单即可。

# 只返回还在起点、发呆(idle)的新兵
def findUnplacedSoldiers():
    friends = hero.findFriends()
    result = []
    for friend in friends:
        if 18 < friend.pos.y and friend.pos.y < 30 and friend.action == "idle":
            result.append(friend)
    return result

8.4.2 列表逐渐变短（The List Keeps Shrinking）

8.4.2.1 每轮结束刷新 recruits Refresh recruits at the end of each round

每轮把一个士兵送去归位后，在循环末尾重新赋值 recruits = findUnplacedSoldiers()。因为刚归位那位已不再 idle，新名单会比上一轮少一个人。这样 recruits 每轮缩短，直到变成空列表——排序也就完成了。

8.5.1 while 空列表停止（Stop When the List Is Empty）

8.5.1.1 用列表长度控制循环 Use list length to control the loop

while len(recruits): 是这道关卡的主循环条件。在 Python 里，非空列表的长度是正数（真），空列表长度是 0（假）。所以只要 recruits 里还有人，循环就继续；一旦所有人都归位、名单变空，len(recruits) 为 0，循环自动停止。这是一种优雅的"处理到没有为止"写法。

# 主循环骨架：还有未归位的新兵就继续
recruits = findUnplacedSoldiers()
markIndex = 0
while len(recruits):
    weakest = minHealthUnit(recruits)       # 选最弱
    hero.command(weakest, "move", markPos(markIndex))  # 归位
    markIndex += 1                          # 序号前进
    recruits = findUnplacedSoldiers()       # 刷新名单

8.5.2 复杂度 O(n²)（Time Complexity）

8.5.2.1 为什么说选择排序"不高效" Why selection sort is not efficient

选择排序简单直观，但效率不高。对 n 个元素，第一轮要在 n 个里找最小，第二轮在 n-1 个里找，第三轮 n-2 个……总比较次数是 n + (n-1) + ... + 2 + 1 = n(n+1)/2，属于 O(n²) 级别。数据翻倍，耗时约变四倍。它适合数据量小、追求代码简单的场景；处理海量数据时，会换用更快的归并排序、快速排序等。

这一节聚焦关卡的策略、思路与算法设计，只展示用于说明的关键片段，完整通关程序请你自己动手完成。

第 17 关 · 成形！

🧊 成形！—— 用选择排序把新兵按身高列队

图2：成形！——8 名新兵杂乱站在城门前，用选择排序每轮选出最矮（血量最低）的一个送到标记处，最终从矮到高列队

策略：反复"选最矮 → 送去下一个空位"

身高与 health 成正比，所以"按身高排"就是"按血量排"。策略就是选择排序：每一轮从还没归位的新兵里挑出血量最低（最矮）的那个，命令他走到最左边还空着的标记处，然后处理下一位。因为最矮的先占最左位、次矮的占其次……最终队形自然从矮到高、从左到右。

最矮

本轮选中→标记0

红色=本轮选出的最弱者，橙色=还未归位。每轮挑走一个，剩下的越来越少。

思路拆解一：写好求最弱者函数

排序的"引擎"是 minHealthUnit。用求最小值算法遍历传入的士兵列表，初始 minHealth = 9001，谁血量更低就更新记录，最后返回最弱的那个单位。这个函数你在前面单元其实已经练过类似的（寻找最低血量友军），迁移过来即可。

# 关键片段：返回 health 最低的单位
def minHealthUnit(units):
    weakest = None
    minHealth = 9001
    for unit in units:
        if unit.health < minHealth:
            minHealth = unit.health
            weakest = unit
    return weakest

思路拆解二：主循环的四个动作

主循环 while len(recruits): 里每轮做四件事，顺序不能乱：① 用 minHealthUnit(recruits) 找出本轮最弱者；② 用 command + markPos(markIndex) 命令他去当前标记；③ markIndex += 1 让位置序号前进；④ 重新 findUnplacedSoldiers() 刷新名单。因为归位的士兵不再 idle，会自动从新名单里消失，名单每轮变短，直到为空、循环结束。

# 关键片段：选择排序主循环的四个动作
while len(recruits):
    weakestRecruit = minHealthUnit(recruits)              # ① 选最弱
    hero.command(weakestRecruit, "move", markPos(markIndex))  # ② 归位
    markIndex += 1                                     # ③ 序号+1
    recruits = findUnplacedSoldiers()                  # ④ 刷新名单

为什么不用手动 remove：标准选择排序需要 unsorted.remove(smallest) 把已排好的移除。但本关里，被命令移动的士兵状态从 idle 变成 move，findUnplacedSoldiers() 就不再把他算进去——相当于"自动移除"。所以每轮只需重新查询名单，无需手动删除元素。

四步顺序别搞乱：必须先选最弱、命令归位、序号+1，最后才刷新名单。如果一开循环就刷新名单、或忘了 markIndex += 1，会导致士兵挤到同一个标记、或反复命令同一个人。归位与序号自增要成对出现。

8.7.1 新手最容易踩的坑（Pitfalls for Beginners）

8.7.1.1 选择排序的典型问题 Typical issues with selection sort

图3：忘刷名单、序号不自增、初值设反、求最弱函数没写全，是本单元最常见的失误