身份证排序算法解析：字符串处理与多关键字排序实战

讲个真实的场景：你在刷题网站上看到一道“身份证排序”，第一反应是这还不简单，直接用字典序排一遍不就完事了吗？真到考场上或者提交系统里跑一遍，你才发现根本不是那么回事。这道题的核心不在“排序”这两个字上，而在“怎么把身份证号里藏的那八位数字准确拎出来，再按正确的规则排”。我当年第一次做这道题的时候，前两次提交都是80分，最后看题解才反应过来，我漏掉的不是排序逻辑，是年份百年和月份补零的细节。

这道题表面上是蓝桥杯算法提高里的VIP题，实际考察的是字符串处理、日期解析和排序稳定性的一锅烩。做熟了之后你会发现，它其实就是在模拟现实里一个非常常见的需求——“给一堆身份证号按出生日期做年龄排序”，只不过场景从业务系统移植到了算法题里。这篇文章我会顺着我的调试过程，把从读题、拆字段、排序选型到提交后踩坑的完整链路都捋一遍，希望能帮你少走一次80分的弯路。

1. 题目本质：你排的不是身份证号，而是“隐藏的生日”

先给没做过这道题的朋友说清楚题目是什么。输入是一堆18位身份证号，要求按出生日期从大到小排序，如果生日相同，再按身份证号本身升序排列。注意，这里有个很容易被忽略的点：输出的不是生日，而是原始身份证号。很多人第一步就把输出结果写成了排序后的日期，白白掉分。

身份证号的第7到第14位是出生日期，格式是四位年份、两位月份、两位日号。比如某位同学的身份证号中间第7到14位是“19990817”，那他的生日就是1999年8月17日。生日越大意味着出生越晚，年龄越小，所以“按出生日期从大到小排序”翻译成人话就是“年龄小的排前面，年龄大的排后面”。

这道题的精髓在于，它考的不是你会不会调用现成的排序函数，而是你会不会在一个可能混有大写字母X的18位字符串里，精准地把子串抠出来，并且保证抠出来的数字在比较时不丢精度、不错位数。我第一次写的时候用的C++的string直接截子串，然后转换成整数去排，思路本身没问题，但是我在排序规则上写反了一个符号，导致整个顺序颠倒了。这种错误在本地测试的时候特别容易漏掉，因为样例数据往往只有三四条，正序倒序看上去都“合理”，只有提交后才发现全错。

另外要特别注意，身份证号里存在最后一位为X的情况，X是大写字母。这个X不参与出生日期的解析，但是在按身份证号字典序做次级排序的时候，ASCII码的比较规则会跟纯数字混在一起。好在C++的字符串比较默认就是按字符的ASCII值逐位比较的，数字字符一定小于大写字母X，所以直接用string比较就能符合“身份证号升序”的要求，不需要单独做映射。

2. 拆分字段：字符串截取的正确姿势与易错点

既然核心在于提取第7到14位，那一步就要时刻提醒自己：字符串的索引是从0开始的，而题目说的第7到14位是从1开始计数的。转换成代码里的下标，就是字符串下标6开始，连续取8个字符。C++里是id.substr(6, 8)，Java是id.substring(6, 14)，Python是id[6:14]。这里特别容易混，我见过不少人是直接substr(7, 8)，那取出来的就是第8到第15位，日期全错位了，结果自然不对。

选对截取方式之后，下一个问题是：这8位到底要不要转成整数？我的建议是，在你需要做“日期的年、月、日拆开比较”时再转，如果只需要整体排序，可以直接把8位字符串当成一个整体来比较。为什么？因为日期字符串“19990817”的字典序恰好和数值大小一致，字符串比较“19990817”>“19980101”等价于日期更晚。这样排序能少一次类型转换，也避免整数溢出风险。18位身份证号整体转整数会溢出，但8位日期转整数完全没问题，所以两种方案都可以过。

不过，如果你像我一样是个喜欢把所有数据“结构化”的人，那就把8位字符串拆成年、月、日三个整数。这一步要特别小心月份和日期的前导零，比如出生日期是2000年3月5日，字符串是“20000305”，直接stoi("03")没问题，结果就是3，不用担心“03”解析不了。但如果你把整个字符串切成三段再用atoi，要确保你没把“2000”“03”“05”切错位置。切错位置的经典症状是：月份和日期差一位，但样例数据恰好不包含个位数月或日，于是你完美地避开了测试点，只能靠WA（Wrong Answer）结果去猜错在哪。

我个人的做法是把结构化后的生日直接拼成一个整数，比如birth = year * 10000 + month * 100 + day，这样比较一次整数就好。这个方法虽然简单，但很实用，而且后续扩展时也方便——比如题目如果改成“按身份证号中的地区码排序”，你只需要把拼接公式改一下即可。

3. 排序策略：结构体排序与比较器设计的三种思维方式

处理这类多关键字排序，行业内习惯有三种做法：结构体加自定义比较器、双关键字排序、以及更“原始”的直接借助稳定排序连续按不同关键字排三次。三种方法各有适用场景，我逐一展开说。

第一种是定义结构体，把身份证号、生日字符串、结构化整数都放进一个结构体里，然后重载小于号或者写一个比较函数。比较函数的逻辑要严格遵循题目顺序：先比生日，生日大的排前面；生日相同再比身份证号，身份证号小的排前面。这个比较器看起来简单，但是不和“正常思维”一致的地方在于，生日是降序，身份证号是升序，两个方向不一样，很容易顺手把第二个比较条件也写成降序，结果就是同一天生日的人身份证号是倒序输出，样例里如果有两条同生日的记录就能看出来，没有的话又是一次隐藏WA。

第二种方法是把两个比较条件合并成一个键。比如把“日期降序”转换成“负日期升序”，这样我们就可以用默认的升序排列，先按负生日排序，再按身份证号升序。本质上就是把多关键字排序硬转成单关键字，代码量会稍微少一些，适合笔试时间紧的时候快速写。

第三种方法是利用排序算法的稳定性：先按身份证号升序排序，再按生日降序做一次稳定排序。因为稳定排序不会打乱前面排序结果中相等元素的相对顺序，所以第一次排好身份证号顺序，第二次按生日排序时，生日相同的记录会自动保持身份证号的升序。这种方法在C++里用stable_sort，在Java里直接用Collections.sort（Java的归并排序是稳定的）也可以。我实习时在某个部门做过一个身份证管理和查询的工具，当时为了不写复杂的比较器，就是靠稳定排序连排两遍来实现的，代码可读性反而更高。

三种方式里我更推荐第一种，因为它最直观，也最能体现你对比较器方向的理解。另外，万一题目数据范围变大或者排序规则微调，结构体加比较器的扩展性最好。

4. 输入输出细节：别在IO上丢掉本不该丢的分

这道题的输入输出格式在蓝桥杯这类OJ上通常比较“原始”。输入第一行是一个整数N，代表身份证号的数量，接下来N行每行是一个18位字符串。输出要求是每行一个排好序的身份证号。虽然听起来很简单，但IO的坑主要隐藏在三个地方。

第一个坑是输入里可能混有空格或者不可见字符。用C++的cin >> string能自动跳过空白符，但如果用gets或者getline，就可能会把换行符残留问题搞出来。特别是有多组测试数据时，你要注意循环里有没有把每一行彻底读完。我总是建议用cin >> id这样的方式读取，方便又安全，不要手动处理缓冲区的换行。

第二个坑是行尾空格，OJ对行尾一般不看，但你输出时不要闲着没事多打一个空格。这样的输出在某些比对模式下会被判为Presentation Error，虽然不算WA，但也烦人。

第三个坑是提前排序。有些人在读入N之后，还没读完所有身份证号就开始处理，一旦数据条数变多，那中间结果会被后续读入覆盖掉。这听起来很蠢，但在循环内边读边排序的写法里确实会出问题。稳妥的做法是先全部存进数组或向量，读完后统一处理。

我自己在提交的时候还遇到过一种情况：局部数组开小了。因为题目里N的数据范围没写清楚，一开始我开了1000个元素的数组，结果后面测试数据一加大就段错误。从那以后我但凡做排序题，习惯性把数组开到最大范围再乘个2，或者直接用动态数组。别在这种地方保守，省内存省不出AC。

5. 我的80分调试经历：一个符号引发的大翻车

这一步我想单独拉出来讲，因为我相信很多人会跟我犯一模一样的错误。我一开始写的比较函数是这样的：

cpp复制bool cmp(const Person& a, const Person& b) {
    if (a.birth != b.birth) {
        return a.birth > b.birth;   // 希望生日大的在前
    }
    return a.id < b.id;             // 身份证号升序
}

本地测试的时候，我给了四条数据，其中两条生日相同，跑出来结果跟我手算的一致，我就觉得稳了。交上去，80分。我盯着那个界面看了半天，脑子里全是问号：逻辑没错啊，输出也对啊，哪里有问题？

后来我拉出错误反馈，发现是第二组测试数据里出现了两个生日相同的身份证号，并且这两个身份证号之间存在“前几位相同、后面不同”的情况。我重新检查代码才发现，我的比较器第一次提交版本里写的是：

cpp复制return a.id > b.id;

也就是身份证号降序。为什么当时本地没测出来？因为我测试用例里那两条相同生日的身份证恰好字典顺序跟降序一致，我给自己的“验证”做了一个非常糟糕的样本选择。从那以后我做排序题，只要涉及正序和降序混在一起，一定会在注释里标清楚“生日降序、号码升序”，并且在造测试数据时专门加一组能区分两种顺序的极端样例。

这件事让我想到一个更通用的经验：当你怀疑自己算法没问题但就是有测试点过不去时，别急着怀疑边界条件，先检查比较方向上有没有写反，尤其是那种“A大在前，B小在后”的组合排序。十个WA里至少有两个是从比较符号这里来的。

另外，我还学到一个更稳妥的验证技巧：造数据时把身份证号最后一位或中间几位故意打乱，制造出“生日相同但字典序不是天然升序”的情况。这比单纯来自网上复制的样例更能检验你的比较器是不是真的严格按题目要求执行。

6. 三种语言的实现对照：从工程视角看同一套逻辑

如果你不是只用C++刷题，那么看看Java和Python的写法也挺有意思，因为同一套比较逻辑在不同语言里会表现出不同的代码风格。

Java里最直接的写法是实现Comparator接口：

java复制class Person {
    String id;
    int birth;
}

Comparator<Person> cmp = new Comparator<Person>() {
    @Override
    public int compare(Person a, Person b) {
        if (a.birth != b.birth) {
            return Integer.compare(b.birth, a.birth);
        }
        return a.id.compareTo(b.id);
    }
};

用Integer.compare(b.birth, a.birth)而不是直接b.birth - a.birth，是为了防溢出。虽然这里birth不会大到溢出，但在你处理其他数值键时这个习惯很值得保留。String的compareTo方法天然实现字典序，符合题目对身份证号的排序要求。

Python里则可以用sorted函数的key参数一口气构造出排序键：

python复制def sort_key(pid):
    birth = pid[6:14]
    return (-int(birth), pid)

这里用负数的方式把生日降序转换成升序，简洁到有些“黑客风”。但要注意，负数取负只能在birth的数值范围内有效，如果birth是字符串，你就不能直接取负，必须先转成整数。这也是为什么我前面说，在需要整体排序时可以把birth当作字符串保留，而需要“日期降序”这种比较时，转整数后用负数最方便。

三种语言对比下来，你会发现同样一道题，C++要写结构体、Java要写比较器、Python只用一个lambda或函数就能搞定。可读性上Python最好，运行效率上C++最稳，Java属于折中。竞赛里选什么语言取决于你熟悉什么，但算法和字符串处理的核心逻辑从来不会因为语言改变，这大概就是练这个题的真正价值所在。

7. 进阶变体：从“身份证排序”延伸出的四道变形题

很多刷题的人做完这一道就草草收场，我觉得挺可惜的。因为“身份证排序”这个模型可以很自然地延展出一整类字符串排序问题。我基于这道题改造过几次，拿来当面试候选人的笔试热身题，下面几个变形方向都挺值得琢磨。

第一个变形是把排序规则改成“按出生日期升序，同生日按身份证号降序”。会做这道题的都会写，但是特别容易一味复述原来的思路，导致比较器只改了一半。这类题的训练价值在于强迫你认真整理比较器的每个分支，而不是机械地替换符号。

第二个变形是要求“提取地区码排序”。身份证前6位是地区码，排序规则改成按地区码分组，组内按出生日期降序。这种题其实是从单关键字排序变成了分组排序，实现思路可以先把地区码截出来当作key，也可以直接用多字段排序。涉及的数据结构会稍微复杂一点，但逻辑框架和原题一致。

第三个变形是处理“非法身份证号”。比如输入的字符串不满18位，或者第7到14位不是合法日期。原题没有这个需求，但实际业务系统里会要求程序做合法性校验。这也提醒我们，竞赛题和真实项目之间还是有一道明显的分界线——别把刷题时的“宽松输入”当成工程里的“合法输入”。那一步校验往往能让你少踩很多坑。

第四个变形是把数据规模放大到百万级，考察排序稳定性或内存占用。如果数据量很大，你就不能把所有数据一次性读进内存再排序，得考虑分块排序后归并，或者用外部排序。这种变形已经脱离原题本身，变成考察工程能力了。我某次改造时试过用生成器逐行读入、分块落盘，最后通过归并得到全局有序，写完后回头再看，循环空间和对象创建方式全都得重新设计，和刷题时完全不是一个难度。

8. 提交前必须自测的四组边界数据

结尾这部分我本来想讲点总结性的东西，后来想想，干巴巴的总结不如给大家一组能直接自测的数据。每次你把这四组数据放到本地跑一遍，能过滤掉绝大多数低级错误，提交通过率会高很多。

第一组是只有一个人的输入。别笑，很多时候代码在多数据情况没问题，偏偏在N=1的时候输出错格式，或者忘了保留原始输入。一个简单的点是，如果只有一行身份证，你的程序至少要正常打印出来。

第二组是生日相同的两条记录，且身份证号末位是X和纯数字各一条。这一组专门用来验证次级排序规则，也是我当年80分的根源所在。如果这组数据你跑出来的顺序跟预期不一致，说明比较器或key构造里方向搞反了。

第三组是最小和最大日期各一条。比如“00010101”和“20991231”，用来验证你截取、转换、排序时有没有把前导零和溢出处理干净。别以为这种极端数据一定不会出现在测试点里，出题人最爱用这样的边界来筛人。

第四组是所有身份证号完全相同。程序得正常输出N行相同的字符串，如果出现死循环或者异常排序，几乎可以断定是排序边界条件没处理干净。

我没有把“测试数据”的细节展开到具体的18位号码，是为了防止大家形成“抄一组数据就跑”的依赖。跑完上面四类场景，你实际上已经覆盖了排序逻辑的绝大多数分支分支。真正代码在OJ上撞出来的WA，多半都隐藏在某个你没生成过的组合里。

做这道题最有价值的收获，其实不是掌握了substr怎么截、比较器怎么写，而是养成了一种对输入字段和排序方向的高度警觉。希望你刷完这篇之后动手重写一遍，用你熟悉的语言把那四组自测数据跑通，再提交一次。手感是自己的，对比分才有意义。