请教一个带“-”的文字编号排序问题

[glaucus]

有 N 条数据，每条数据有一个形如 1-1-2，10-3-1 ... 的编号，同时也可能有 3-2，5-8 这种的，请问对这些编号进行排序？有什么效率比较高的算法？

[0ZXYDDu796nVCFxq]

需求描述不准确，驳回重写需求

[RRRoger]

加字段辅助排序

[momocraft]

别管效率，先想清楚你想要的排序结果

[msaionyc]

x-y-z 应该是 x-y 的子分支吧？如果是的话
1.筛选出 x-y 结构的编号，建立基本结构（ map，tree)
2.筛选出 x-y-z 的编号，挂到步骤 1 下，并手写一个排序 y-z 的函数
以上需要自己建立数据结构 or 类，保证可以构建合适的函数来对 x-y-z 这样的编号进行排序，比较大小。

[sobigfish]

我觉得你可以参考下 Semantic Versioning 的排序算法
当然前面的是主要的排序只是我猜的

[glaucus]

@gstqc #1
@momocraft #3
@msaionyc #4 是的，就是类似 Word 文档里的章节编号一样，是有分支关系的

[glaucus]

@sobigfish #5
@momocraft #3
@RRRoger #2 当前的想法是先按最大位数把位数补齐，比如最长的是 3-2-1-1 就把其它的比如 3-2 补到 3-2-0-0，再把每一个数据的位数不起，比如 3-5-2 补成 03-05-02 （已确定每一个数字最多两位），然后把中间的“-”去掉解析成数字直接比较数字大小，但是感觉有点繁杂，不知道有没有更优雅的做法

[msaionyc]

比较数字的话，10，20 这类不好解决啊，对了，如果最大不超过 26，可以使用 a-z 进行映射然后字符串排序就可以解决了，如果再大的话就要采取其他手段了

[msaionyc]

编号很大的话，比如到几十，上百这种，建立树形结构也还算是比较好解决的

[Ukonwnothing]

@msaionyc 好奇在 V2EX 中回复层主是层主增加铜币还是楼主增加铜币？？

[qcts33]

不知道题主用什么语言，我只是提一句 python 可以直接对比 list，不同长度都行……
原理是逐位对比，直到出现不同，如果出现不同之前有一个序列结束了，短的小

[shench]

php natsort 这个函数试一下

[VictorJing94]

格式化,然后排序?

[thesharjah]

1. 如果分段数有限且每段内数字在一定范围内，可以考虑转换成 int 来排序；比如 1-1-2 => 001001002 => 1001002
2. 如果不满足 1，php version_compare 函数试试，效率不确定，但实现简单

[rrfeng]

各种库都带接口啊，自己写一个 compare 不就行了吗？

[glaucus]

@shench #12 试了一下，感觉挺符合需求的，正好用的 PHP，感谢
@thesharjah #14 natsort 可行，version_compare 还没试
@rrfeng #15 我就是在请教自己写 compare 的实现细节

[Lin0936]

mark 一下，之前也有这种需求，而且编号最大数是 5000+，总共十万多条，沿用了之前代码里的版本对比函数。等一个好点的方法。

[Doldrums]

在 sql 遇到的话我估计会这么操作
1.统计“-”的数量 AS Level [例如 3-2-1：L2 3-2：L1]
2.去除“-” trans 为纯数字 AS No. [例如 3-2-1：321 3-2：32]
3.两列排序

[whileFalse]

对于 x-y-z，如果 x、y、z 均在 100 以内，则比较 x*10000 + y* 100 + z 即可。

[annielong]

数据库的话最好建辅助字段，如果数组的话解析后再排序

[AlisaDestiny]

```java
public class Test {

public static void main(String[] args) {
new Test().test1();
}
public void test1(){
ArrayList<String> list = new ArrayList<>();
list.add("2-3");
list.add("1-3-3");
list.add("2");
list.add("4-3-3-2");
list.add("1-2-3");
list.add("1");
list.add("2-4");
list.add("5-3-3");
list.add("2-3-1");
list.sort((o1, o2) -> {
String[] s1 = o1.split("-");
String[] s2 = o2.split("-");
int mLen = Math.min(s1.length,s2.length);
for(int i=0;i<mLen;i++){
int a = Integer.parseInt(s1[i]);
int b = Integer.parseInt(s2[i]);
if (a != b){
return a - b;
}
}
return (s1.length - s2.length);
});
System.out.println(list);//[1, 1-2-3, 1-3-3, 2, 2-3, 2-3-1, 2-4, 4-3-3-2, 5-3-3]
}
}
```

[tantalu]

都有数据范围的，果断桶排序

[wxb2dyj]

先去掉-，原下划线之间的数字不够两位的补齐为两位，然后桶排序，时间复杂度 O(n)，排好序后再补-，去掉多余的 0

[wxb2dyj]

@wxb2dyj 说错了，应该用基数排序。

[no1xsyzy]

多维链表简单插排不就行了？
要觉得这样效率不行链表部分换堆

[fsafdasfsdafsd]

分隔，排序。