V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
sdenvi
V2EX  ›  问与答

请教:各种排序算法效率的问题

  •  
  •   sdenvi · 2017-05-10 11:41:11 +08:00 via iPhone · 2248 次点击
    这是一个创建于 2733 天前的主题,其中的信息可能已经有所发展或是发生改变。
    大家工作中遇到排序的时候一般采用什么样的一种方式,效率如何?对字符进行排序的时候遇到相同的字符又是采用哪种排序效率比较高?
    13 条回复    2017-05-10 16:03:44 +08:00
    jy02201949
        1
    jy02201949  
       2017-05-10 11:52:08 +08:00
    待会又有人来帖教你如何 google 的网址了,话说字符排序是什么情况,字符串么?
    geelaw
        2
    geelaw  
       2017-05-10 11:53:38 +08:00
    我一般用电脑排,用手排序的时候一半用归并。
    lany
        3
    lany  
       2017-05-10 11:56:06 +08:00 via Android
    我一般用 Excel 点一下升序就好了
    xj998
        4
    xj998  
       2017-05-10 11:59:40 +08:00 via Android
    用 Linux 命令就行了。
    as463419014
        5
    as463419014  
       2017-05-10 12:00:55 +08:00
    放到数据库里,order by,[手动滑稽]
    coderluan
        6
    coderluan  
       2017-05-10 12:01:52 +08:00
    单纯研究算法效率就看复杂度呗,工作中遇到肯定是拿来主义,如果真遇到大量数据需要排序,一般都是优先考虑能分解和并行的算法的。
    sdenvi
        7
    sdenvi  
    OP
       2017-05-10 13:29:27 +08:00 via iPhone
    @coderluan 今天去面试,面试官问到一个问题,就是给个乱序的字符串,里面可能包含相同的字符,对其进行正序或者倒序排列,是不是应该把字符串中相同的字符先放到一起再去考虑排序的问题?
    coderluan
        8
    coderluan  
       2017-05-10 13:46:35 +08:00
    这个啊,不是那个 acm 水题吗,只不过把整数换成了字符,这题根本是排序,而是结构转换。
    简单来说,就是你弄个 bool 的字母表,先全设置成 0,然后读输入字符串,碰见个字符,就把字母表相应位置,设成 1,重复不重复的无所谓,最后把字母表中为 1 的字符全输出就是结果了,因为字母表本身都是按顺序来的。
    holyghost
        9
    holyghost  
       2017-05-10 13:46:45 +08:00
    @sdenvi 这个用桶排,时间 O(n)空间 O(1)
    coderluan
        10
    coderluan  
       2017-05-10 13:53:49 +08:00
    上面说的可能比较混乱,假设字母就有 a,b,c,d,e 五个,那样你开始申请个 A[0] = {0,0,0,0,0}。
    碰见了输入 cdbd,那样数组的变化就是 {0,0,1,0,0}, {0,0,1,1,0}, {0,1,1,1,0}, {0,1,1,1,0}最后把 1 的位输出,就是 bcd 了。
    thundernet8
        11
    thundernet8  
       2017-05-10 14:12:03 +08:00 via iPhone
    以数组排序为例,不考虑数值特殊性,用归并排序的迭代方式比较好,时间和空间都控制的不错,在几个常见排序算法里面,接近快排的时间消耗
    starqoq
        12
    starqoq  
       2017-05-10 16:00:59 +08:00 via Android
    @coderluan
    @thundernet8
    建一棵字母树,然后遍历一下就好了。
    coderluan
        13
    coderluan  
       2017-05-10 16:03:44 +08:00
    @starqoq #12 用不到树,字符本身就是线性顺序
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   998 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 20:16 · PVG 04:16 · LAX 13:16 · JFK 16:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.