Swift SE-0372 解读：官方承诺 `sort()` 为稳定排序，从文档变更看标准库行为保证

Swift SE-0372 解读：官方承诺sort()为稳定排序，从文档变更看标准库行为保证

【免费下载链接】swift-evolutionThis maintains proposals for changes and user-visible enhancements to the Swift Programming Language.项目地址: https://gitcode.com/gh_mirrors/sw/swift-evolution

SE-0372（Document Sorting as Stable）是 Swift 标准库演进提案中少见的"纯文档型"提案——它不改任何算法与 API，只是把早已是事实的行为正式写入文档承诺。本文以该提案为骨架，结合 swift-evolution 仓库中的关联提案与演进背景，系统讲解稳定排序（stable sort）的定义、sort()的实现现状、该保证对源码兼容性与 ABI 的意义，以及多属性排序等真实应用场景。

提案背景与核心结论

SE-0372 的提案文本位于 proposals/0372-document-sorting-as-stable.md，作者为 Nate Cook，评审经理为 Tony Allevato，状态为Implemented（Swift 5.8 落地）。参考仓库 README.md 中的版本表，Swift 5.8 于 2023-03-30 正式发布，即该文档承诺随 5.8 一同生效。

提案的核心主张非常直接：

Swift 的排序算法在 Swift 5 之前就已经被改为稳定排序，但文档从未给出这一保证。让我们正式承诺排序算法是稳定的，让开发者可以依赖该行为。

换句话说，这是一次"将既有事实写进文档"的规范化操作，而不是引入新能力。

什么是稳定排序（Stable Sort）

稳定排序是指：对于比较结果相等（或无法比较）的元素，排序后保持它们原有的相对顺序。提案给出了一个极具代表性的例子——球员名单已按姓氏排序，再按名字排序后，两位名为 "Ashley" 的球员仍保持原来的先后次序（Hatch 在 Sanchez 之前）：

var roster = [ Player(first: "Sam", last: "Coffey"), Player(first: "Ashley", last: "Hatch"), Player(first: "Kristie", last: "Mewis"), Player(first: "Ashley", last: "Sanchez"), Player(first: "Sophia", last: "Smith"), ] roster.sort(by: { $0.first < $1.first }) // roster == [ // Player(first: "Ashley", last: "Hatch"), // Player(first: "Ashley", last: "Sanchez"), // Player(first: "Kristie", last: "Mewis"), // Player(first: "Sam", last: "Coffey"), // Player(first: "Sophia", last: "Smith"), // ]

若排序不稳定，两次 "Ashley" 的相对位置可能被任意打乱，结果变得不可预测。

稳定性何时可被观察到

提案明确指出，排序稳定性并非总能被察觉：

• 当集合依据元素自身的Comparable一致性排序时（例如排序一个整数数组），"相等"的元素通常无法区分，稳定性几乎不可见；
• 只有当元素基于其属性的子集进行排序时，稳定性才产生可观察的差异。

例如上面的球员示例，若按完整身份（名字+姓氏）比较，两个 "Ashley" 并不相等，稳定性无从谈起；只有仅按first排序时，first相等的两个元素才需要靠稳定性保持原始相对顺序。

为什么稳定性符合直觉：电子表格的多列排序

提案提到一个重要的用户预期来源：电子表格软件。在表格中先按某一列排序、再按另一列排序，是完成多属性复合排序的惯用方式。这种操作能否得到预期结果，完全依赖于每次排序的稳定性。开发者从这类工具迁移到编程语言时，会天然期待排序保留相等元素的相对顺序；而许多经典排序算法（如快速排序）并不稳定，这种认知落差正是提案所指的"surprising"。

现状问题：行为早已稳定，文档却明确否认

提案引用了 Swift 5.7 标准库Sort.swift中一段著名的文档注释：

The sorting algorithm is not guaranteed to be stable. A stable sort preserves the relative order of elements that compare as equal.

即：文档明确声明"不保证稳定"，但实现早就稳定了。这个状态造成了两类问题：

1. 了解稳定性的开发者：无法依赖当前行为——理论上，任何一个 Swift 版本都可能"修正"文档而改用不稳定算法，使依赖稳定性的代码静默出错；
2. 不了解稳定性的开发者：一旦稳定性在未来被移除，他们的程序会突然出现难以排查的"随机 bug"。

正式保证稳定性可以同时消除这两类风险。

解决方案：一处文档注释的变更

由于 Swift 5 之前（即 ABI 稳定之前）就已引入稳定排序，所有当前 Swift 运行时版本都自带稳定排序，因此本提案只需修改标准库文档，不涉及任何实现改动：

- /// The sorting algorithm is not guaranteed to be stable. A stable sort + /// The sorting algorithm is guaranteed to be stable. A stable sort /// preserves the relative order of elements that compare as equal.

这个 diff 是提案全文最核心的交付物，体现了"标准库行为承诺"的本质：sort()与sorted()自此获得正式的、可持续依赖的行为契约。与之配套的实现合入为 apple/swift 的 PR #60936。

兼容性影响分析

源码兼容性

该变更只是把既有行为固化为契约，因此对所有现有源码完全兼容——此前能编译运行的代码，之后依然能编译运行，且行为不变。

ABI 稳定性

稳定排序的实现在 ABI 稳定（Swift 5 正式确立 ABI 稳定）之前就已就位，因此所有 ABI 稳定的 Swift 版本本来就已经提供该行为。对二进制层面毫无影响。

API 韧性（API resilience）

这是唯一产生"约束"的维度：一旦做出明确保证，未来任何对排序算法的修改都必须维持稳定性，稳定性从"实现细节"升级为"公共 API 契约的一部分"。这正是把行为文档化的价值——它约束的是 Swift 团队未来的演进自由，换取的是全体开发者的确定性。

备选方案：为什么不做unstableSort()

讨论排序稳定性时，自然会出现一个疑问：既然稳定性这么好，是不是也应该提供一个不稳定的排序变体unstableSort()？提案给出了清晰的否决理由：

• 不稳定本身没有价值：没有任何用户需要"把相等元素打乱"的排序；
• 用户真正感兴趣的可能是具有其他特性的算法，例如只使用数组现有内存分配（in-place、零额外分配）的排序，这类算法在不要求稳定的前提下更容易实现、性能更优；
• 若未来有人提出这类排序算法提案，其不稳定性完全可以通过文档说明和/或 API 命名来传达（例如在命名中显式体现非稳定特性），无需让默认排序让步；
• 默认sort()保持稳定，依然是最符合直觉、最安全的选择。

未来方向：排序生态的更多可能

提案在结尾列举了若干值得继续探索的排序相关改进，这些方向至今仍是 Swift 标准库演进的活跃话题：

• key-path 或基于函数的排序：允许直接按\.property这样的 key path 排序，减少闭包样板；
• 有序集合类型或协议（sorted collection types / protocols）：把"始终有序"提升为一等公民的数据结构能力；
• 排序描述符（sort descriptors）：支持可组合、可复用的比较条件描述。

值得注意的是，仓库中已有若干与排序生态直接相关的历史提案可供交叉参考，例如 SE-0074（二分查找函数） 提出的partitionedIndex(where:)、sortedIndex(of:)、sortedRange(of:)与partition(where:)，它们都建立在"集合已有序"的前提之上——而有序的前提，正是依赖sort()的确定性；SE-0078（rotate 算法） 则探讨了与排序同属基础算法的旋转操作。这些提案共同勾勒出 Swift 在"有序数据"方向上的完整演进脉络。

实践要点：如何在代码中利用稳定性保证

从 Swift 5.8 起，你可以放心地在生产代码中依赖以下行为：

1. 多键复合排序（两阶段排序）

先按次要键排序，再按主要键排序；稳定保证使两次排序的结果等价于一次多键排序：

players.sort(by: { $0.last < $1.last }) // 次要键 players.sort(by: { $0.first < $1.first }) // 主要键，稳定保留上一步顺序

2. 结合partition(where:)等 API 的有序集合操作

当使用 SE-0074 讨论的partitionedIndex(where:)这类算法时，其正确性要求集合元素已按谓词完成分区或有序排列，稳定的sort()是构建这一前提的可靠工具。

3. 无额外依赖的排序链

sort()（原地）与sorted()（返回新数组）共享相同的稳定性契约，因此以下写法同样是安全的：

let stable = players.sorted { $0.score > $1.score }

小结

SE-0372 是 Swift Evolution 进程中"文档即契约"理念的典型样本：它以一行文档注释的变更，把 Swift 社区长期默认的稳定排序行为正式化，消除了标准库行为与文档表述之间长达数个版本的鸿沟。对开发者而言，从 Swift 5.8 起，"sort()是稳定排序"不再是一个"碰巧成立的实现细节"，而是一条可以放心依赖、写进任何业务逻辑与算法假设的官方承诺。

【免费下载链接】swift-evolutionThis maintains proposals for changes and user-visible enhancements to the Swift Programming Language.项目地址: https://gitcode.com/gh_mirrors/sw/swift-evolution