基于新空数组的多条件排序算法选型及置换映射可行性咨询

1. 一步完成排序+复制的可行算法 #

既然你的数组已经按名称字典序排好，完全可以利用这个预排序特性，直接构建符合新条件的目标数组，不用先复制再整体排序：

• 基于索引排序构建新数组：先生成一个和原数组长度一致的索引数组（比如[0,1,2,...,n-1]），然后按新的排序规则对这个索引数组排序（比较时用原数组对应索引的元素做判断）。排序完成后，遍历这个索引数组，依次把原数组的元素取出放到新空数组里。这个过程把排序和复制合并成了一步，而且因为只排序整数索引，比直接排序对象数组开销小很多；如果新排序条件和原有序性有关（比如新条件是原条件的次级排序键），还可以在索引排序时利用原有序性减少比较次数（比如两个元素新条件相同时，直接用原数组的顺序，不用再比较原键）。
• 分组追加法：如果新排序规则是“原排序键作为主条件，新增键作为次条件”，那原数组已经是主条件有序的，你可以遍历原数组，把同主条件的元素归为一组，每组内按次条件排序，然后直接把排序后的组依次追加到新数组里。这种方法跳过了整体排序的开销，完全是边处理边构建新数组。

2. 置换映射（索引数组）的性能分析 #

用置换映射（也就是只存排序后的索引，不复制原数组）是否更优，要看你的使用场景：

• 优势场景：
  • 当对象体积很大时，复制整个数组的内存开销远大于保存一个整数索引数组；
  • 需要同时维护多个排序视图（比如电话簿要支持姓氏、电话、住址三种排序），只需要存三个索引数组，不用复制三份对象数组，能省大量内存；
  • 原数组元素很少修改的情况，生成一次索引数组后可以反复使用。
• 劣势场景：
  • 如果需要频繁按某个排序条件遍历元素，索引数组的间接访问（先取索引再找原元素）会比直接遍历排序后的对象数组慢，因为缓存命中率更低；
  • 如果对象体积很小（比如只有几个基本类型字段），复制数组的开销和索引数组的开销相差不大，甚至直接复制排序更快。

3. 多条件排序的落地建议 #

针对电话簿这类需要多条件排序的场景，推荐这么做：

• 维护原数组的同时，预先生成并保存对应每个排序条件的索引数组；
• 生成索引数组时用稳定排序，利用原数组的有序性减少比较次数（比如按电话号码排序时，号码相同的元素直接保留原数组的姓氏顺序）；
• 如果业务需要实际的排序后数组，再根据对应的索引数组一次性构建；如果只是需要按排序顺序遍历，直接用索引数组取原元素即可，不用额外复制。

内容的提问来源于stack exchange，提问作者Gyro Gearloose