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

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

  •  1
     
  •   glaucus · 9 天前 · 1149 次点击

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

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