` 为稳定排序，从文档变更看标准库行为保证)
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-evolutionSE-0372Document Sorting as Stable是 Swift 标准库演进提案中少见的纯文档型提案——它不改任何算法与 API只是把早已是事实的行为正式写入文档承诺。本文以该提案为骨架结合 swift-evolution 仓库中的关联提案与演进背景系统讲解稳定排序stable sort的定义、sort()的实现现状、该保证对源码兼容性与 ABI 的意义以及多属性排序等真实应用场景。提案背景与核心结论SE-0372 的提案文本位于 proposals/0372-document-sorting-as-stable.md作者为 Nate Cook评审经理为 Tony Allevato状态为ImplementedSwift 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.即文档明确声明不保证稳定但实现早就稳定了。这个状态造成了两类问题了解稳定性的开发者无法依赖当前行为——理论上任何一个 Swift 版本都可能修正文档而改用不稳定算法使依赖稳定性的代码静默出错不了解稳定性的开发者一旦稳定性在未来被移除他们的程序会突然出现难以排查的随机 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-0078rotate 算法 则探讨了与排序同属基础算法的旋转操作。这些提案共同勾勒出 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
