求个排序算法

[jianghu52]

有数组如下
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次冒泡才能得到最后的目标数组。
想请问还有没有更加快捷的办法能得到最后的目标数组。

[iloahz]

先将每类控件单独排序，这个在数据库那层做应该很方便吧，然后跑多路归并就好了。这样应该是逻辑最简洁的了，O(nlogn + nlogk)的时间复杂度，O(n)的额外空间，其中k为控件类别数。

个人更偏向这样：

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

这样时间复杂度是O(n + nlogn)，O(k)的额外空间，而且目测实际运行比前面那个算法快。

[jianghu52]

@iloahz 恩，看起来确实有点快。我sql不是很强，一直不是很敢用sql完成业务逻辑。都是放在php这边做的。我试试看用sql的思路来排序看看

[yyai3]

尝试：SELECT c1 FROM t1 order by left(c1,4),c1