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

求个排序算法

  •  
  •   jianghu52 · 2013-09-11 09:22:44 +08:00 · 2397 次点击
    这是一个创建于 4093 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有数组如下
    a_list={
    [0]=>1,1,radio1;
    [1]=>2,0,text;
    [2]=>4,2,radio2
    [3]=>5,1,radio3;
    [4]=>6,2,radio4;
    [5]=>7,1,checkbox1;
    [6]=>8,2,checkbox2;
    [7]=>11,1,checkbox11;
    }
    解释下这个二维数组。整个数组表示的一些控件在页面中的分布顺序。
    第一维是控件在数据库中的物理顺序。
    第二维,
    第一项:控件在页面显示的顺序(唯一,但是不连贯)
    第二项:控件归属的组,比如radio1同radio3是归属一组的。checkbox1与checkbox11也是一组
    第三项:控件名
    希望有个算法能得到如下结果
    a_list={
    [0]=>1,1,radio1;
    [1]=>5,1,radio3;
    [2]=>2,0,text;
    [3]=>4,2,radio2
    [4]=>6,2,radio4;
    [5]=>7,1,checkbox1;
    [6]=>11,1,checkbox11;
    [7]=>8,2,checkbox2;
    }
    即:radio或者checkbox存在的情况下,以该控件为基准,同组的控件位置提前,其他控件位置依次向后窜。
    我现在的做法很笨:
    1.查询数据库得到radio跟checkbox的两个数组。每个数组分别保存了位置最小,而且归属组不同的控件。具体到这个例子。
    radio_list{
    [0]=>1,1,radio1;
    [1]=>4,2,radio2
    }
    checkbox_list{
    [0]=>7,1,checkbox1;
    [1]=>8,2,checkbox2;
    }
    2.分别循环每个数组,然后再在里面做冒泡排序。(当然,还有要判断先循环谁的问题)
    以这个例子来说,我要做4次冒泡才能得到最后的目标数组。
    想请问还有没有更加快捷的办法能得到最后的目标数组。
    3 条回复    1970-01-01 08:00:00 +08:00
    iloahz
        1
    iloahz  
       2013-09-11 10:23:13 +08:00   ❤️ 1
    先将每类控件单独排序,这个在数据库那层做应该很方便吧,然后跑多路归并就好了。这样应该是逻辑最简洁的了,O(nlogn + nlogk)的时间复杂度,O(n)的额外空间,其中k为控件类别数。

    个人更偏向这样:

    1. 扫一遍得到每类控件的最小位置
    2. 自定义compare函数:
    1. 若最小位置不同,返回最小位置小的
    2. 返回位置小的
    3. 跑快排

    这样时间复杂度是O(n + nlogn),O(k)的额外空间,而且目测实际运行比前面那个算法快。
    jianghu52
        2
    jianghu52  
    OP
       2013-09-11 10:47:25 +08:00
    @iloahz 恩,看起来确实有点快。我sql不是很强,一直不是很敢用sql完成业务逻辑。都是放在php这边做的。我试试看用sql的思路来排序看看
    yyai3
        3
    yyai3  
       2013-09-11 11:27:21 +08:00   ❤️ 1
    尝试:SELECT c1 FROM t1 order by left(c1,4),c1
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5819 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 06:29 · PVG 14:29 · LAX 22:29 · JFK 01:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.