V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
glaucus
V2EX  ›  程序员

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

  •  1
     
  •   glaucus · 2019-04-16 10:07:32 +08:00 · 2339 次点击
    这是一个创建于 2037 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    26 条回复    2019-04-17 21:12:20 +08:00
    0ZXYDDu796nVCFxq
        1
    0ZXYDDu796nVCFxq  
       2019-04-16 10:12:57 +08:00 via Android
    需求描述不准确,驳回重写需求
    RRRoger
        2
    RRRoger  
       2019-04-16 10:13:45 +08:00   ❤️ 2
    加字段辅助排序
    momocraft
        3
    momocraft  
       2019-04-16 10:14:38 +08:00
    别管效率,先想清楚你想要的排序结果
    msaionyc
        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 这样的编号进行排序,比较大小。
    sobigfish
        5
    sobigfish  
       2019-04-16 10:20:19 +08:00   ❤️ 1
    我觉得你可以参考下 Semantic Versioning 的排序算法
    当然前面的是主要的排序只是我猜的
    glaucus
        6
    glaucus  
    OP
       2019-04-16 10:24:39 +08:00
    @gstqc #1
    @momocraft #3
    @msaionyc #4 是的,就是类似 Word 文档里的章节编号一样,是有分支关系的
    glaucus
        7
    glaucus  
    OP
       2019-04-16 10:30:29 +08:00
    @sobigfish #5
    @momocraft #3
    @RRRoger #2 当前的想法是先按最大位数把位数补齐,比如最长的是 3-2-1-1 就把其它的比如 3-2 补到 3-2-0-0,再把每一个数据的位数不起,比如 3-5-2 补成 03-05-02 (已确定每一个数字最多两位),然后把中间的“-”去掉解析成数字直接比较数字大小,但是感觉有点繁杂,不知道有没有更优雅的做法
    msaionyc
        8
    msaionyc  
       2019-04-16 10:44:27 +08:00
    比较数字的话,10,20 这类不好解决啊,对了,如果最大不超过 26,可以使用 a-z 进行映射然后字符串排序就可以解决了,如果再大的话就要采取其他手段了
    msaionyc
        9
    msaionyc  
       2019-04-16 10:45:37 +08:00   ❤️ 1
    编号很大的话,比如到几十,上百这种,建立树形结构也还算是比较好解决的
    Ukonwnothing
        10
    Ukonwnothing  
       2019-04-16 10:50:59 +08:00
    @msaionyc 好奇在 V2EX 中回复层主是层主增加铜币还是楼主增加铜币??
    qcts33
        11
    qcts33  
       2019-04-16 10:51:30 +08:00   ❤️ 1
    不知道题主用什么语言,我只是提一句 python 可以直接对比 list,不同长度都行……
    原理是逐位对比,直到出现不同,如果出现不同之前有一个序列结束了,短的小
    shench
        12
    shench  
       2019-04-16 11:10:04 +08:00   ❤️ 1
    php natsort 这个函数试一下
    VictorJing94
        13
    VictorJing94  
       2019-04-16 11:11:29 +08:00   ❤️ 1
    格式化,然后排序?
    thesharjah
        14
    thesharjah  
       2019-04-16 11:59:55 +08:00   ❤️ 1
    1. 如果分段数有限且每段内数字在一定范围内,可以考虑转换成 int 来排序;比如 1-1-2 => 001001002 => 1001002
    2. 如果不满足 1,php version_compare 函数试试,效率不确定,但实现简单
    rrfeng
        15
    rrfeng  
       2019-04-16 12:40:28 +08:00
    各种库都带接口啊,自己写一个 compare 不就行了吗?
    glaucus
        16
    glaucus  
    OP
       2019-04-16 13:38:20 +08:00
    @shench #12 试了一下,感觉挺符合需求的,正好用的 PHP,感谢
    @thesharjah #14 natsort 可行,version_compare 还没试
    @rrfeng #15 我就是在请教自己写 compare 的实现细节
    Lin0936
        17
    Lin0936  
       2019-04-16 13:49:31 +08:00
    mark 一下,之前也有这种需求,而且编号最大数是 5000+,总共十万多条,沿用了之前代码里的版本对比函数。等一个好点的方法。
    Doldrums
        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.两列排序
    whileFalse
        19
    whileFalse  
       2019-04-16 14:05:19 +08:00
    对于 x-y-z,如果 x、y、z 均在 100 以内,则比较 x*10000 + y* 100 + z 即可。
    annielong
        20
    annielong  
       2019-04-16 14:08:50 +08:00
    数据库的话最好建辅助字段,如果数组的话解析后再排序
    AlisaDestiny
        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]
    }
    }
    ```
    tantalu
        22
    tantalu  
       2019-04-16 19:16:17 +08:00
    都有数据范围的,果断桶排序
    wxb2dyj
        23
    wxb2dyj  
       2019-04-17 02:00:31 +08:00 via iPhone
    先去掉-,原下划线之间的数字不够两位的补齐为两位,然后桶排序,时间复杂度 O(n),排好序后再补-,去掉多余的 0
    wxb2dyj
        24
    wxb2dyj  
       2019-04-17 02:05:13 +08:00 via iPhone
    @wxb2dyj 说错了,应该用基数排序。
    no1xsyzy
        25
    no1xsyzy  
       2019-04-17 10:08:09 +08:00
    多维链表简单插排不就行了?
    要觉得这样效率不行链表部分换堆
    fsafdasfsdafsd
        26
    fsafdasfsdafsd  
       2019-04-17 21:12:20 +08:00
    分隔,排序。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1053 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 20:05 · PVG 04:05 · LAX 12:05 · JFK 15:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.