《算法的乐趣》第十九节

本节首先用反证法证明了Gale-Shapley算法的正确性：算法结束后不可能有人单身，因为单身的男人必然求过婚，而单身的女人不可能拒绝任何求婚；同样……

本节首先用反证法证明了Gale-Shapley算法的正确性：算法结束后不可能有人单身，因为单身的男人必然求过婚，而单身的女人不可能拒绝任何求婚；同样，结果中不可能存在一对彼此更喜欢对方而非当前伴侣的男女，因为求婚规则会促成他们配对。由此证明算法得到的是稳定匹配。

随后以舞伴问题为例介绍了算法的应用与实现。n个男孩和n个女孩各提交一份按偏爱程度排序的名单，主持人需将他们配对成稳定的舞伴关系。实现时为每个舞伴定义偏爱列表、当前伴侣和下次邀请对象等属性，用FindFreePartner()寻找未配对的男孩，用GetPerfectPosition()判断女孩对某舞伴的偏爱程度（位置越靠前越喜欢）。对于不在偏爱列表中的对象，该函数返回一个极大值来统一处理，避免代码中出现繁琐的特殊判断，类似排序中的"哨兵"技巧。

接着讨论了优化：原实现中每次都要遍历偏爱列表，可预先构建二维表priority[w][m]记录m在w偏爱列表中的位置，将查询降为O(1)，即"以空间换时间"。最后指出稳定匹配不唯一：改变男女优先策略或调整男孩顺序都会得到不同的稳定匹配。完美匹配数量最多为n!，但偏爱列表的约束使许多组合重复，实际稳定匹配数远少于此。