根本原因是默认字符串比较按 Unicode 码点顺序执行,与任何语言的字母表都不同;JavaScript / Python / Java / SQL 默认比较器均受影响。
Álvarez 排在 Zetterberg 后面。Öberg 在列表最底部。排序执行了,产生了稳定的顺序,没有报错;它只是按一个与任何语言的字母表顺序都无关的数字来排序。
所有带变音符号的字符都在底部
这个 bug 的特征是:列表看起来正确,直到末尾——一小簇带变音符号的名字出现在 Z 之后,顺序看起来是随机的。其实并非随机的:这是 Unicode 码点的顺序,而且完全 deterministic(确定性)。
生成的代码在每种语言中默认都会产生这个问题,因为字符串的默认比较运算符是码元比较——JavaScript 中不带比较器的 Array.prototype.sort()、Python 中的 sorted()、Java 中的 String.compareTo,以及 SQL 中使用字节排序校对的列上的 ORDER BY。这些都没有坏。只是在回答一个与界面所提问题不同的问题。
默认排序实际比较的是什么
非重音拉丁大写字母位于 U+0041 到 U+005A。带重音的拉丁字母位于 Latin-1 Supplement 及之后的区块,从 U+00C0 开始,带抑扬符和其他附加符号的字母所在位置更高:
A U+0041 Z U+005A
Á U+00C1 Ä U+00C4 Å U+00C5
Ö U+00D6 Ø U+00D8 Š U+0160
因此每个带重音的大写字母都排在所有非重音字母之后,这就是为什么它们聚集在底部。注意:Å(U+00C5)在码点顺序中大于 Ä(U+00C4),这与瑞典字母表的顺序相反——所以即使是底部簇的内部顺序,对于其来源的语言也是错误的。
同一列表,三种顺序
取这个八姓列表,用三种方式排序:
input Andersson, Álvarez, Ärlig, Åberg, Öberg, Østergaard,
Zetterberg, Šimek
code point Andersson
Zetterberg <- Z (U+005A) 在所有重音字母之前
Álvarez (U+00C1)
Ärlig (U+00C4)
Åberg (U+00C5)
Öberg (U+00D6)
Østergaard (U+00D8)
Šimek (U+0160)
Swedish Álvarez á 的主权重为 a
Andersson
Šimek š 的主权重为 s
Zetterberg
Åberg Å, Ä, Ö 是字母表的第 27、28、29 个字母
Ärlig 排在 Z 之后
Öberg
Østergaard ø 在瑞典语中与 ö 排序相同
German Åberg 字典顺序 (DIN 5007-1):
Álvarez ä, ö, ü 排序为 a, o, u
Andersson
Ärlig
Öberg
Østergaard
Šimek
Zetterberg
三个完全不同的结果,而且只有第一种对所有人来说都是错的。瑞典语和德语顺序都是正确的——分别对瑞典语和德语读者而言。Árlig 在瑞典语排倒数第二,在德语中排第一,输入相同。
没有唯一正确的顺序
这是设计时必须接受的现实,而且令人不安,因为它意味着"这个列表排序正确吗?"这个问题在没有指定"对谁来说"之前没有答案。
瑞典语、丹麦语、挪威语和芬兰语将带重音的元音视为独立字母,排在 Z 之后。丹麦语和挪威语将它们排序为 Æ、Ø、Å;瑞典语将它们排序为 Å、Ä、Ö。
德语有两种标准顺序。DIN 5007-1(字典顺序)将 ä 视为 a。DIN 5007-2(电话本顺序)将 ä 视为 ae,这会改变 Müller 和 Mueller 等名字的相对位置。两者都是标准,用于不同场景。
西班牙语将 ñ 作为一个独立字母直接放在 n 之后,所以 Peña 排在 Pena 之后、Pera 之前。Ch 和 ll 在 1994 年皇家语言学院(Real Academia Española)决定之前也是独立字母,所以旧索引和新索引的排序不同。
爱沙尼亚语的情况表明这不仅仅是关于重音:Z 在爱沙尼亚字母表中位于 S 和 T 之间,所以爱沙尼亚语的列表不仅仅是把英语的重音移一移位置而已。
捷克语和斯洛伐克语将 č、ř、š 和 ž 视为独立字母,跟在各自的基础字母后面,所以 Šimek 在那里不会像在瑞典语中那样与 S 排序在一起。
所有这些都被收录在 Unicode 排序算法(Unicode Collation Algorithm,UTS #10)及其在 CLDR 中按语言区域的调整中。该算法的结构使得德语和瑞典语的结果都能表达:它在多个级别进行比较,主要级别是基础字母,后面的级别处理重音和大小写,语言区域的调整改变了给定符号在哪个级别起作用。在德语中,变音符是次要差异;在瑞典语中,它是主要差异。
规范化使情况更糟
在排序正确之前,输入必须处于一致的 Unicode 形式。Ö 可以是一个码点 U+00D6,也可以是两个——O 后跟 U+0308 COMBINING DIAERESIS(组合分音符)——两者显示起来完全相同。
在码点排序下,这两种形式落在完全不同的位置:分解形式与普通 O 相邻,排在列表中间;而预组合形式则到底部。因此列表可能包含同一个名字两次,出现两个位置,看起来完全相同。这与对名字字段进行长度检查会对同一个名字返回不同判定是同一个根本问题,修复方法也相同:在输入时规范化为 NFC。
校对数据是有版本的,改变版本会重新排序索引。glibc 2.28 版本更改了许多语言区域的校对定义,使在旧规则下构建的受影响系统的现有 PostgreSQL 索引失效——这是一个真实的、广泛遇到的操作风险,而非理论问题。如果你的数据库按系统校对排序,操作系统升级就是数据排序事件。
在各层修复
JavaScript。传递用 Intl.Collator 构建的比较器,绝不要用裸的 sort():list.sort(new Intl.Collator(locale).compare)。在需要忽略大小写或自然数字排序的地方添加 sensitivity 和 numeric 选项。
PostgreSQL。在列上或查询中使用 ICU 校对,而不是数据库默认校对——默认往往是 C 语言区域或系统语言区域,会随系统移动。在不同主机上 ORDER BY surname COLLATE "sv-SE-x-icu" 是明确的且稳定的,而默认校对则不是。
存储一种形式,按另一种形式排序。存储的名字属于用户;排序键是你的。在显示名字旁边保留一个规范化、语言区域校对过的排序键,使顺序可重现,并允许你在不触碰源数据的情况下更改校对规则。
决定列表使用谁的字母表。对于单一市场产品,使用该市场的语言区域。对于多语言产品,使用查看者的语言区域——这意味着同一列表对两个用户可以合法地有不同的顺序,任何引用位置("第三行")或按字母范围分页的 UI 都必须考虑到这一点。
不要让模型对列表进行排序。它会产生一个看似合理的顺序,但在调用之间不可重现,对于超过一屏的列表,它会悄悄删除或重复行。排序是一个已解决的确定性问题,每种平台都有正确的实现。
波兰语的情况有其自己的一套调整规则,值得单独阅读《Polish diacritics and sort order》,存储端的问题也值得一读《normalising accented names in a database》。
Why Polish Diacritics Break Naive String Sorting