有 N 条数据,每条数据有一个形如 1-1-2,10-3-1 ... 的编号,同时也可能有 3-2,5-8 这种的,请问对这些编号进行排序?有什么效率比较高的算法?
1
0ZXYDDu796nVCFxq 2019-04-16 10:12:57 +08:00 via Android
需求描述不准确,驳回重写需求
|
2
RRRoger 2019-04-16 10:13:45 +08:00 2
加字段辅助排序
|
3
momocraft 2019-04-16 10:14:38 +08:00
别管效率,先想清楚你想要的排序结果
|
4
msaionyc 2019-04-16 10:16:42 +08:00
x-y-z 应该是 x-y 的子分支吧?如果是的话
1.筛选出 x-y 结构的编号,建立基本结构( map,tree) 2.筛选出 x-y-z 的编号,挂到步骤 1 下,并手写一个排序 y-z 的函数 以上需要自己建立数据结构 or 类,保证可以构建合适的函数来对 x-y-z 这样的编号进行排序,比较大小。 |
5
sobigfish 2019-04-16 10:20:19 +08:00 1
我觉得你可以参考下 Semantic Versioning 的排序算法
当然前面的是主要的排序只是我猜的 |
6
glaucus OP |
7
glaucus OP |
8
msaionyc 2019-04-16 10:44:27 +08:00
比较数字的话,10,20 这类不好解决啊,对了,如果最大不超过 26,可以使用 a-z 进行映射然后字符串排序就可以解决了,如果再大的话就要采取其他手段了
|
9
msaionyc 2019-04-16 10:45:37 +08:00 1
编号很大的话,比如到几十,上百这种,建立树形结构也还算是比较好解决的
|
10
Ukonwnothing 2019-04-16 10:50:59 +08:00
@msaionyc 好奇在 V2EX 中回复层主是层主增加铜币还是楼主增加铜币??
|
11
qcts33 2019-04-16 10:51:30 +08:00 1
不知道题主用什么语言,我只是提一句 python 可以直接对比 list,不同长度都行……
原理是逐位对比,直到出现不同,如果出现不同之前有一个序列结束了,短的小 |
12
shench 2019-04-16 11:10:04 +08:00 1
php natsort 这个函数试一下
|
13
VictorJing94 2019-04-16 11:11:29 +08:00 1
格式化,然后排序?
|
14
thesharjah 2019-04-16 11:59:55 +08:00 1
1. 如果分段数有限且每段内数字在一定范围内,可以考虑转换成 int 来排序;比如 1-1-2 => 001001002 => 1001002
2. 如果不满足 1,php version_compare 函数试试,效率不确定,但实现简单 |
15
rrfeng 2019-04-16 12:40:28 +08:00
各种库都带接口啊,自己写一个 compare 不就行了吗?
|
16
glaucus OP @shench #12 试了一下,感觉挺符合需求的,正好用的 PHP,感谢
@thesharjah #14 natsort 可行,version_compare 还没试 @rrfeng #15 我就是在请教自己写 compare 的实现细节 |
17
Lin0936 2019-04-16 13:49:31 +08:00
mark 一下,之前也有这种需求,而且编号最大数是 5000+,总共十万多条,沿用了之前代码里的版本对比函数。等一个好点的方法。
|
18
Doldrums 2019-04-16 13:55:33 +08:00
在 sql 遇到的话我估计会这么操作
1.统计“-”的数量 AS Level [例如 3-2-1:L2 3-2:L1] 2.去除“-” trans 为纯数字 AS No. [例如 3-2-1:321 3-2:32] 3.两列排序 |
19
whileFalse 2019-04-16 14:05:19 +08:00
对于 x-y-z,如果 x、y、z 均在 100 以内,则比较 x*10000 + y* 100 + z 即可。
|
20
annielong 2019-04-16 14:08:50 +08:00
数据库的话最好建辅助字段,如果数组的话解析后再排序
|
21
AlisaDestiny 2019-04-16 15:06:04 +08:00 1
```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] } } ``` |
22
tantalu 2019-04-16 19:16:17 +08:00
都有数据范围的,果断桶排序
|
23
wxb2dyj 2019-04-17 02:00:31 +08:00 via iPhone
先去掉-,原下划线之间的数字不够两位的补齐为两位,然后桶排序,时间复杂度 O(n),排好序后再补-,去掉多余的 0
|
25
no1xsyzy 2019-04-17 10:08:09 +08:00
多维链表简单插排不就行了?
要觉得这样效率不行链表部分换堆 |
26
fsafdasfsdafsd 2019-04-17 21:12:20 +08:00
分隔,排序。
|