拖拽排序的算法思考

作者: | 更新日期:

一个同事问我有没有了解过拖拽排序,于是讨论了下,发现挺有意思的,记录一下。

一、背景

今天有同事问我:有没有做过用db一个字段来做排序索引,然后支持用户随意更改排序的需求?

起初看到这个问题,我以为是按照一个字段排序,然后支持人工干预。

不过一想,不对,人工干预了就没办法按照指定字段排序了。 一旦人工干预,所以字段的位置都固定了。

那个同事说,就是所有位置都固定,但是需要支持拖拽排序。
需要维护一个排序索引字段,不知道有没有成熟的类似的算法?

需求简化一下就是,有一批数据储存在DB中,会删除一条数据或插入一个数据,希望有个算法能够储存这个顺序。

二、字符串排序

最简单的是每次插入的时候,修改所有数据的编号。 不过这个数据储存在DB中,一条记录一行,修改所有数据的编号的复杂度是 O(n)了,数据少还可以,多了不能接受。

接着我想,如果使用整数的话,可能会冲突。冲突了还需要调整局部区间的标号,怪复杂的。 但是使用字符串的话,冲突了就加后缀即可,简单粗暴。 于是我提供了第一个方法:字符串中值+后缀解决。

比如对于下面的数据

p0001
p0004
p0005
p0009

p0001 拖到 p0005之后, 通过计算 (p0005p0009)的值,得到 p0007
p0001 拖到 p0004之后,通过计算(p0004p0005)的值,得到 p00045

同事看之后,说:使用字符串排序比较慢。

三、整数

我想,这个建个索引的话,复杂度还是log(n)的,只是常数比较大。 非要使用整数的话,还是使用上面的中值方法,只不过冲突的时候,需要进行小范围重调整了。

当然,我们可以使用32位整数或者64整数来当做编号,需要人工拖拽的数据量一般是人一个个加进去的,一般也就十几条,顶多几百条。
冲突的概率是非常小的,使用32位整数就够了。
于是,使用这个方法差不多就解决问题了。

四、储存率

然后,我又思考:如果到了冲突那一步才进行调整,可能情况已经很坏了。 如果能够提前就进行调整,平均复杂度应该会更低。

怎么判断是否需要调整呢?
我引入了一个储存率的概念。

设第 i 个数字的值是 P(i),第 j 个数字的值是 P(j),则(i,j)的储存率就是 (j - i + 1)/(P(j) - P(i) + 1)。
储存率越高,冲突的概率越大。

然后,每次调整位置后,检查新插入位置在局部小区间的储存率是否超过指定值,超过了就在局部大区间进行调整。

当然,这个只是我的猜测,没有数学公式证明这个平均复杂度更低。

五、浮点数

后来,想了想,使用浮点数也可以降低冲突的概率。
但是冲突的久了,还是需要进行区间调整的。

六、分块

有序数据或者数组,其本质还是递归形式的链表。
但是使用裸的链表性能显然是不能接受的。

于是我想可以使用ACM中常使用的分块思想。
分块+链表,自然想到了分块链表。

但是考虑具体实现细节的时候,发现在DB中维护链表的关系成本蛮高的。
每个链表节点需要有一个唯一标示,这个唯一标示需要快速定位到链表节点的首地址。
首地址的元素可能会删除,那还需要使用双向链表。
虽然方案是可行,但是实现成本太高,实现了代码也太复杂,不可行。

接着,我想,数组既然是链表,那链表也是数组了。
于是我就想到了分块数组。

每个分块有一个唯一的标号,标号的大小顺序代表分块的顺序。
这个就转化为了两个字段来决定数据顺序了。

第一级的标号是分块,每个分块内独立进行分配标号。这样冲突的概率就大大的降低了。 有多低呢? 原先的数量级是O(N),现在降为了srqt(N)
而且维护两级的成本比一级的成本高不了多少。

七、最后

有一周没写东西了,其实那一周也没看书。
最近杂事变得很多很多,把很多计划都打乱了,以至于我都怀疑人生了:我在干什么?
还好,现在敲了一些代码后慢慢恢复正常了。

后面会多写一些算法上的东西,有利于提高思维能力。

本文首发于公众号:天空的代码世界,微信号:tiankonguse-code。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越