自然排序算法：让文件名里的数字按大小排队

你有没有在文件管理器里遇到过这种诡异场面同一批文件明明看着应该老老实实按顺序排结果 File 10 硬生生站到 File 2 前面Chapter 11 排在 Chapter 3 前面log10.log 排在 log2.log 前面。我第一次被这个问题坑是在整理某个项目的日志文件时。当时我盯着文件列表对时间线死活想不通为什么 log10 会在 log2 之前还以为文件管理器抽风了。后来才明白这不是工具坏了而是它默认走了字典序lexicographic order——一种完全不认识数字大小的排序方式。这篇文章想聊的自然排序natural sort order正是为了解决这类问题而生的算法把文件名里的数字部分当成数值去比较让排序结果符合人类直觉。不管你是写代码的、做运维的还是经常被一长串带编号文件折磨的普通用户搞懂这个算法都能帮你少踩不少排序的坑。1. 先搞清楚字典序为什么把 File 10 排在 File 2 前面1.1 一个每天都在发生的小尴尬我复现一下那种场景。假设你有一批发布会素材命名格式是“素材2.jpg”“素材3.jpg”“素材10.jpg”。在图形界面的文件管理器里素材3 后面跟着素材10你感觉顺理成章。可一旦切到终端执行排序命令列表却变成素材10、素材2、素材3、素材10 在最前面。同一批文件两种完全不同的顺序不懵才怪。再举一个追剧的例子某部动画片下载下来是“第9集.mp4”“第10集.mp4”文件管理器里把第10集排在最后但在某些命令行工具里第10集会被扔到第1集后面和第2集前面。你以为第10集和第9集是前后脚结果它跑到最前面当老大哥去了。这类现象的本质是操作系统或者软件在排序时选择了不同的比较规则。图形文件管理器为了照顾用户习惯通常默认启用自然排序而很多命令行工具、脚本、数据库和办公软件默认沿用经典的字典序。字典序是一种标准的字符串比较方式几乎所有编程语言都内置支持。问题在于字符串比较按的是一个字符一个字符的编码顺序并不理解“10”这个字符串背后代表的数值含义。所以当你看到“File 10 排在 File 2 前面”时先不要怪工具。它很可能只是诚实地执行了字典序而字典序从来就不打算理解数字。1.2 字典序的比较规则一次只看一个字符字典序的比较逻辑听起来很简单从字符串的第一个字符开始逐个比较两个字符串对应位置的字符编码大小一旦分出高低就结束后面的字符不再看。英语里字符比较的大小通常按 ASCII 码来理解。数字字符“0”到“9”的 ASCII 码是 48 到 57大写字母“A”到“Z”是 65 到 90小写字母“a”到“z”是 97 到 122。Unicode 的前 128 个码位和 ASCII 完全一致所以日常英文文件名的比较基本就是按这个顺序走。现在用这个规则比较“File 10”和“File 2”F 和 F 相同i 和 i 相同l 和 l 相同e 和 e 相同空格和空格相同轮到数字字符左边的1对应 ASCII 49右边的2对应 ASCII 50。49 小于 50比较结束。结论就是“File 10”小于“File 2”排序时“File 10”排在前面。即使文件名没有空格写成“File10”和“File2”也是一样的结果因为比较到第 5 个字符时仍然是1和2在比。问题出在哪里出在“10”被拆成了两个字符字符串比较先看见的是第一个字符1而不是整个数值 10。计算机不认识“10”这个符号组合表示十它只认识编码表里1在2前面这个事实。于是“10”这个串天然要比“2”这个串小哪怕数值上 10 明明更大。这就像查字典时不是按词义大小排而是按字母在字母表中的编号排。所有以 A 开头的词永远在最前面完全不管后面的字母组成了什么含义。用生活类比理解就是你去图书馆找书书脊上的编号如果是文本形式管理员按字符串排序结果是“10 号书架”排在“2 号书架”前面因为1比2小。数值语义被文本形式盖过了。1.3 “反直觉”不一定错但要看场景字典序被称为字典序和字典编排方式有关。它有一些很突出的优点规则简单、不依赖语言、解析成本低、在任何环境里都能给出确定性结果。对程序内部使用的标识符、枚举值、代码键名而言字典序非常省心也不会因为语言环境不同产生顺序漂移。但文件名是给用户看的。用户看到“第10集”心里想的是十不是字符1加字符0。带编号的日志、素材、备份文件一大把时字典序产生的列表在人类眼里就是乱的。于是自然排序出现了——它要解决的核心问题只有一个让文本里的数字按数值大小参与排序而不是按字符编码排序。理解了这个前提接下来就能顺理成章地讨论自然排序怎么做。2. 自然排序让程序按人类的直觉来排2.1 自然排序的规则定义自然排序没有一个官方标准不同实现之间会有一点细节差异但核心规则基本一致。我习惯把它总结成四条从左到右扫描字符串把连续的数字字符组成一个“数字块”其余字符视为“文本块”。两个字符串逐块比较。文本块之间用普通字符串规则比较数字块之间按数值大小比较。如果数字块的数值相同再根据前导零数量或原始数字字符串长度打破平局。具体策略可以自己定义但必须规则一致。如果一个字符串比较完所有块之后恰好是另一个字符串的前缀那么较短的那个排在前面。这套规则听上去不复杂但它是很多排序问题的答案。比如“File 2”和“File 10”分块之后就是“File”加数字2和“File”加数字10。文本块“File”相同数字块 2 和 10 按数值比2 小于 10于是 File 2 排在 File 10 前面符合人类预期。用表格对比一下字典序和自然序对同一组输入的行为输入样例字典序结果自然排序结果File 2 / File 10File 10 在前File 2 在前movie.9 / movie.10movie.10 在前movie.9 在前log2 / log10 / log1log1、log10、log2log1、log2、log10a1b10 / a1b2a1b10 在前a1b2 在前你会发现自然排序不是把整个字符串当数字处理而是只把其中连续的数字片段拎出来单独判断。这样“a1b2”和“a1b10”这类多段数字的文件名也能排得明明白白。2.2 核心思路数字块与文本块交替比较自然排序最精华的部分在于“分块”。拿“File 10.txt”和“File 2.txt”举例。先用正则或者扫描的方式把它们拆开“File 10.txt”拆成文本块“File ”数字块“10”文本块“.txt”。“File 2.txt”拆成文本块“File ”数字块“2”文本块“.txt”。比较的时候先从第一个文本块开始“File ”和“File ”相同接着比数字块“10”和“2”按数值比是 10 大于 2。所以第二个字符串排前面。文本块“.txt”甚至不需要比。再举一个多段数字的例子“a1b2”和“a1b10”。拆块之后是“a”“1”“b”“2”对比“a”“1”“b”“10”。前面三块都相同最后一块是数值 2 和数值 102 小于 10所以“a1b2”排在“a1b10”前面。这个思路延伸下去能处理相当复杂的文件名。比如“report-3-final-v2.pdf”和“report-3-final-v12.pdf”拆出来的数字块分别是 3、2 和 3、12。前面的“report-3-final-v”都相同最后比 2 和 122 胜出。注意这里比较的是整个字符串中“每一个”数字块不是只找第一个数字。如果只处理第一个数字遇到多段数字时就会出错。2.3 一些容易被忽略的细节自然排序看起来简单但真上手写代码有几个细节不交代清楚很容易翻车。第一个是大小写。自然排序规则本身没有规定大小写怎么处理。两个文件名“File 2.txt”和“file 10.txt”如果直接按原始字符比较大写的 F 和小写的 f 不同可能永远轮不到数字块上场。实际项目里我一般建议先统一大小写再进入分块比较这样用户通常更满意。第二个是排序稳定性。如果两个文件的自然排序结果完全一样比如“file.001”和“file.1”都映射成数值 1那么谁在前谁在后就得靠稳定排序算法来兜底。Python 的sorted是稳定的会保留原列表中的相对顺序但在不支持稳定排序的环境里你需要自己注意。第三个是不同人对“相同数值”的排序预期不一致。有人希望“v001”排在“v1”前面因为 001 看起来更多有人希望“v1”在前因为更简洁。没有标准答案只有产品规则。最好在实现前就把这个策略定下来写进注释免得三个月之后自己都忘了当初为什么这么排。第四个更隐蔽文件名里出现中文数字比如“第一集”“第二集”“第十集”。自然排序只认识阿拉伯数字字符根本不认识“十”是 10。所以中文数字排序不在自然排序的解决范围内它需要专门的语言排序规则或自定义映射。3. 手写实现Python 和 JavaScript 两种方案3.1 Python最经典的 re.split 方案Python 标准库里没有内置自然排序但实现一个够用的版本只需要很短代码。最经典的做法是用正则re.split把字符串按数字切成列表然后让数字块以整数形式参与比较。import re def natural_key(s: str): return [ int(part) if part.isdigit() else part.lower() for part in re.split(r(\d), s) if part ! ]用法也很简单files [File 2.txt, File 10.txt, file 1.txt] print(sorted(files, keynatural_key)) # 输出: [file 1.txt, File 2.txt, File 10.txt]re.split(r(\d), s)的作用是把字符串按数字拆开同时因为捕获括号的存在数字部分会被保留在结果列表里。比如“File 10.txt”经过这一步会变成[File , 10, .txt]。接下来列表推导式把纯数字的字符串转成int非数字部分转成小写字符串于是“10”和“2”比较时就变成整数 10 和 2 比较。这个简单版本覆盖了绝大多数日常文件名场景缺点也很明显。第一如果两个字符串在对应位置一个是数字块、一个是文本块比如“10”和“a2”这种极端情况Python 3 会直接抛TypeError因为整数和字符串不能比较大小。第二前导零会被失掉int(001)和int(1)相等这意味着“v001”和“v1”分不出先后。大部分场景下这两个缺点可以容忍但如果你的数据里混着各种奇葩命名建议用下一节的健壮版。3.2 Python健壮版比较函数为了处理跨类型比较和前导零问题我写过一个比较函数思路是给每个 token 加一个“类型标记”。数字块标记为 0文本块标记为 1。比较时若类型不同数字块优先排前若类型相同再按各自规则比较。数字块内部先比数值数值相同再比原始数字字符串长度前导零少的排前面。import re from functools import cmp_to_key def _parse(s: str): s s.lower() parts re.split(r(\d), s) tokens [] for part in parts: if part : continue if part.isdigit(): stripped part.lstrip(0) value int(stripped) if stripped else 0 tokens.append((0, value, len(part))) # 数字块 else: tokens.append((1, part, 0)) # 文本块 return tokens def natural_compare(a: str, b: str) - int: ta, tb _parse(a), _parse(b) for x, y in zip(ta, tb): if x[0] ! y[0]: return x[0] - y[0] # 数字块排在文本块前 if x[0] 0: if x[1] ! y[1]: return 1 if x[1] y[1] else -1 if x[2] ! y[2]: return 1 if x[2] y[2] else -1 else: if x[1] ! y[1]: return 1 if x[1] y[1] else -1 return 1 if len(ta) len(tb) else (-1 if len(ta) len(tb) else 0) # 使用示例 files [v1.10.tar.gz, v1.9.tar.gz, v1.2.tar.gz, v1.001.tar.gz] print(sorted(files, keycmp_to_key(natural_compare)))这段代码的思路不复杂。每个 token 是一个三元组第一项是类型第二项是比较主值第三项是数字原始长度。数字块和文本块相遇时我选择让数字块在前这是为了让“10abc”这类以数字开头的文件名排在“abc10”前面更接近字典序直觉。如果你希望文本块在前把返回语句改成return y[0] - x[0]就行但需要确保整个项目里只用一种规则。我实际测试这个函数时遇到过“10”和“a2”这种极端输入简单版直接报错健壮版则给出稳定结果[a2, 10]或者[10, a2]取决于你的类型优先级。这个细节在日常文件名里很少遇到但写通用工具时必须有定义。3.3 JavaScript用 Intl.Collator 一行搞定如果写前端代码事情会简单很多。JavaScript 的Intl.Collator是标准内置能力开启numeric选项后就带上了自然排序的核心能力。const collator new Intl.Collator(undefined, { numeric: true, sensitivity: base, }); const files [File 10.txt, File 2.txt, file 1.txt]; files.sort(collator.compare); console.log(files); // 输出: [file 1.txt, File 2.txt, File 10.txt]sensitivity: base让比较忽略大小写和重音这是文件名排序里很常见的需求。numeric: true让连续数字被当成数值处理。这个方案的优点是简单、支持多语言、不需要手写解析逻辑。缺点在于不同运行环境的 ICU 版本不一样排序细节可能不完全一致。尤其当文件里带着特殊字符、全角数字、或者其他语言字符时同一个Collator在不同浏览器里可能给出不同结果。另外numeric: true对前导零的处理策略是强制的你不能自己定义“v001”排在“v1”前面还是后面。所以如果业务对排序规则有严格要求建议还是自己手写。3.4 JavaScript手写版正则 BigInt我给出自己常用的手写实现。它比Intl.Collator复杂一些但排序行为完全可控也不会因为运行环境不同而漂移。function naturalCompare(a, b) { const re /(\d)/g; const ta a.toLowerCase().split(re).filter(Boolean); const tb b.toLowerCase().split(re).filter(Boolean); for (let i 0; i Math.min(ta.length, tb.length); i) { const ca ta[i]; const cb tb[i]; const na /^\d$/.test(ca); const nb /^\d$/.test(cb); if (na nb) { const va BigInt(ca); const vb BigInt(cb); if (va ! vb) return va vb ? -1 : 1; // 数值相同前导零更少的排前面 if (ca.length ! cb.length) return ca.length - cb.length; } else if (na ! nb) { return na ? -1 : 1; // 数字块优先 } else { if (ca ! cb) return ca cb ? -1 : 1; } } return ta.length - tb.length; } const files [File 10.txt, File 2.txt, file 1.txt]; console.log(files.sort(naturalCompare)); // 输出: [file 1.txt, File 2.txt, File 10.txt]这段代码里有几个值得注意的点。用BigInt而不是Number转数字是避免精度问题。如果文件名里出现长数字串比如时间戳“20240101120000”Number可能会超出安全整数范围导致排序出错。BigInt没有这个问题代价是性能稍慢但文件名排序的场景几乎感知不到。split(re)配合带捕获组的全局正则在 JavaScript 中会把匹配到的数字部分也保留在结果数组里。比如“File 10.txt”会被拆成[File , 10, .txt]所以filter(Boolean)可以把空字符串过滤掉。数字块相遇时先比数值数值相同再比原始字符串长度。这样“v1”会排在“v001”前面因为我让更短的原始数字串优先。如果你想反着来把ca.length - cb.length改成cb.length - ca.length即可。这个选择就是典型的产品策略问题代码里一定要注释清楚。4. 边界情况别让自然排序在细节上翻车4.1 前导零问题前导零是最容易被忽视的边界情况。比如“v001”和“v1”数值都是 1按数值比较它们相等。如果你用的实现只比较数值排序后两者谁在前取决于排序算法是否稳定。稳定时原列表里谁先出现谁在前面不稳定时顺序随机这在某些场景里会让人抓狂。我在一个跨平台小工具里测试时发现同一个文件列表在 Python 实现和某前端实现中排出的顺序不同就是因为两边对前导零的处理策略不一样。Python 版本把“v1”排前面因为数字长度短前端版本把“v001”排前面因为它在字符串层面先比较。最后统一成“数值相同按原始数字字符串长度升序”问题才解决。建议你在实现自然排序时明确回答这个问题数值相同的数字块谁的优先级更高我常用的规则是前导零更少的排前面也就是“1”在“001”前面。理由很简单文件名是给人看的名字越简洁的越靠前比较符合日常直觉。但如果你是处理某些固定宽度编码的文件比如“0001_xxx”“0002_xxx”保持前导零不看直接按数值排也完全可以。关键是规则一致。4.2 负数、小数、版本号负数在文件名里特别容易踩坑。文件名里的“-”字符更多时候是连字符或者分隔符比如“report-final-v2.pdf”里就有连字符。如果自然排序把“-2”解析成负数那“file -2.txt”和“file 2.txt”的比较结果会完全出乎意料。我的建议是通用文件名自然排序不要处理负数把“-”当作普通文本字符。如果业务真的需要负数排序比如排序温度记录“-10、-2、0、5”那应该走专门的数值排序而不是文件名自然排序。小数点也有类似问题。“3.5.txt”里的点号是扩展名分隔符不是小数点。通用文件排序如果尝试把“3.5”当作小数处理会闹笑话。因为“3.5.txt”拆块之后应该是文本块“3.”、数字块“5”、文本块“.txt”而不是小数“3.5”。所以写自然排序实现时千万不要把点号纳入数字块。版本号则是另一个独立话题。很多人以为自然排序就能完美处理版本号其实不够。比如“v1.9.0”和“v1.10.0”普通自然排序会先把“v1.”拆掉然后数字块 9 和数字块 10 比较结果正确v1.9.0 在前。但如果你遇到“v1.0rc2”这种带字母后缀的版本自然排序会把 rc 当作文本块整体比较结果通常也还能接受。真正需要小心的是“1.0.3”和“1.0.10”这类带多个点号的字符串。如果实现把“1.0.3”整体拆成一个数字块 1、0、3把“1.0.10”拆成 1、0、10那么比较结果正确如果实现误把“1.0.3”当成小数 1.0 加文本“3”就会出错。稳妥的做法是版本号排序时先按点号分段再对每一段分别做自然排序。这和单纯的文件名自然排序不同需要单独写函数。4.3 中文文件名、大小写、重音符号与 Unicode自然排序只解决“阿拉伯数字和普通文本混排”的问题它不负责语言排序。中文文件名排序通常按拼音或者笔画这需要语言敏感的排序规则自然排序看到的是 Unicode 码点差异和拼音顺序完全是两码事。比如“安全报告”和“版本说明”自然排序只会比较“安”和“版”的码点不会去管哪个拼音先。业务里要排中文名请使用专门的 collation 或拼音排序方案。大小写处理要提前统一。我建议比较前统一转成小写避免“File”和“file”被当作不同文本。如果你希望大小写敏感的排序那整个算法就走另一套规则。重音符号和 Unicode 归一化也值得注意。字符“é”在 Unicode 里有两种表示方式一种是单个预组合字符一种是“e”后面跟一个组合重音符号。两者显示效果一样但码点不同。如果不做归一化同一个文件名在不同系统里可能因为编码方式不同被排到不同位置。处理方法是排序前先做 NFC 或 NFD 归一化具体选哪个看你的业务环境但至少要在整个流程里保持一致。5. 系统与工具的真实排序行为5.1 文件管理器看着“聪明”命令行看着“原始”很多图形文件管理器默认启用自然排序所以普通用户很少觉得文件列表有问题。这也是为什么一旦有人切换到终端看到 ls 输出的顺序会一头雾水图形界面里 File 2 在 File 10 前面命令行里反过来了。终端工具为了简洁和可预测通常会保持字典序。不少终端命令其实已经提供了“版本排序”参数本质就是更严格版本的自然排序专门处理带版本号的文件名。遇到日志文件或者带编号文件时显式加上这个参数顺序就会正常。我自己的建议是脚本里不要依赖默认排序凡是需要按名称排序的文件列表显式指定排序规则避免不同环境下行为不一致。图形界面和终端的差异本质是两种排序策略的问题不是谁对谁错。理解这一点后看到两边顺序不一样就不会再怀疑系统坏了。5.2 表格软件与数据库里的坑在表格软件里处理一列编号经常遇到 File10 排在 File2 前面。原因通常是这一列被当成文本格式存储。文本格式的列升序排序走的是字典序数值格式的列才会按数值大小排。如果这一列混着文本和数字排序结果往往会先文本后数字或者变成字典序。解决办法很直接加一个辅助列把文件名里的数字部分提取成数值再按辅助列排序。也可以用第 5.3 节要讲的零填充技巧把文本数字统一成同等宽度这样文本排序就能得到自然顺序。数据库的情况类似。默认排序规则一般由 collation 决定多数场景下是字典序所以数据库里对“v2”“v10”这类字符串排序结果会不符合业务预期。在 SQL 里用正则表达式把数字转成数值再排序处理少量数据没问题但数据量大时性能堪忧而且很难走索引。更好的方案是在写入时维护一列“排序键”把文件名预先转换成适合字典序的键字符串查询时直接按这一列排序既稳定又能用索引。5.3 零填充技巧把自然序转成字典序的通用方案如果你不想在排序时解析数字还有一个很实用的技巧把数字部分统一补零到固定宽度让字典序的结果恰好等于自然排序的结果。这个思想在很多系统内部被大量使用。原理很简单。数字按数值比较等价于把所有数字都填充成相同位数后按字符串比较。比如把数字补零到 20 位2 变成 0000000000000000000210 变成 00000000000000000010然后按字典序比较这两个字符串前面的若干个 0 相同接着比“2”和“1”2 比 1 大于是 2 排在 10 后面。这和数值 2 小于 10 的顺序完全一致。Python 实现只需要一个正则import re def natural_sort_key(s: str) - str: return re.sub(r(\d), lambda m: m.group(1).lstrip(0).zfill(20), s)这里先lstrip(0)把原有前导零去掉再统一zfill(20)。这样“v001”和“v1”会映射到同一个排序键排序时保持原顺序适合“不关心前导零顺序”的场景。如果业务里必须区分“v001”和“v1”就不能用这个简单技巧需要自定义键生成逻辑。这个技巧最大的优势是可以用在任何只能做字典序排序的环境里数据库排序列、表格辅助列、某些不支持自定义比较器的工具。它也有两个明显限制一是负数和小数不管用因为负号和小数点会被当作普通文本字符二是填充宽度必须足够大超过业务里可能出现的最长数字串。写死在代码里的话一旦数字超过 20 位就可能排序错误所以我把 20 定义成一个常量并写清楚上限。6. 实操经验我的避坑清单6.1 问题快速排查表我把自己遇到过的典型排序问题整理成一个速查表方便你对照排查现象原因对策File 10 排在 File 2 前面走了字典序按字符编码比较换用自然排序或版本排序v001 和 v1 谁在前不稳定数值相同但前导零策略不统一排序前明确规则并在实现里注释表格软件里 10 排在 2 前该列被当成文本格式加辅助列转数值或用零填充技巧图形界面和终端顺序不一致图形界面默认自然排序终端默认字典序脚本显式指定排序规则é 和 e 加重音排在不同位置Unicode 归一化不一致排序前统一做 NFC 或 NFD 归一化v1.9.0 排到 v1.10.0 后面版本号被当作普通数字串处理按点号分段每段分别自然排序这张表里最后一行值得多说一句。普通自然排序对“v1.9.0”和“v1.10.0”其实能得出正确结果因为点号被当作文本数字块 9 和 10 正常比较。真正容易踩坑的是“1.0rc2”这类带字母后缀的版本或者“1.0.3”和“1.0.10”混合出现时某些实现会把点号误当成小数解析。所以版本号排序我总会单独写函数不直接复用通用文件排序。6.2 什么时候别用自然排序自然排序不是万能的。我一开始写项目时恨不得所有排序都用自然排序后来发现有几个场景明显不适合。版本号排序应该用专门的版本比较算法或者至少按点号分段后再逐段自然排序。随意套用文件排序遇到“1.0a”“2.0b1”这类后缀会飘。IP 地址排序要先按四段数值分别排不能直接对“192.168.1.100”整个字符串做自然排序。虽然自然排序能分出“192.168.1.2”和“192.168.1.10”的前后但和真正的 IP 排序语义还是有区别遇到 IPv6 更得小心。人名、单位名称的排序要交给语言文化的排序规则拼音、笔画、或按 locale 排序都不是自然排序该管的事。中文文件名里的中文数字同理“第三集”和“第十集”自然排序无能为力需要额外映射。程序内部使用的枚举键名、状态码、ID 排序我建议继续保留字典序。这类排序追求的是确定性和可排查性不追求人类直觉字典序在跨语言跨平台时更稳。6.3 我的个人选择与实用小技巧做了这么多排序相关的事情我现在的习惯是凡是展示给用户看的文件名列表默认用自然排序但只固定一种实现绝不混用多个库避免平台差异。凡是程序内部维护的键、ID、索引继续用字典序稳定可控最重要。最后分享一个我后来一直在用的小技巧归档文件名时提前用零填充规则生成一个排序号。比如原始文件名是 log10.txt我在归档记录里额外存一列排序键“log00000000000000000010.txt”。以后不管是数据库查询、脚本处理还是导出表格随便按字符串排序都不会翻车。这个习惯帮我免掉了无数后续麻烦。自然排序本身不难难的是把边界条件想清楚并在团队里把规则固定成共识。希望这篇文章能让你下次再看到 File 10 排在 File 2 前面时一眼就明白背后的来龙去脉顺手说出那句经典台词这是字典序不是自然序。