拖拽排序的算法思考

一、背景

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

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

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

那个同事说，就是所有位置都固定，但是需要支持拖拽排序。

需要维护一个排序索引字段，不知道有没有成熟的类似的算法？

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

二、字符串排序

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

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

比如对于下面的数据

p0001
p0004
p0005
p0009

p0001 拖到 p0005 之后， 通过计算 （ p0005 ， p0009 ）的值，得到 p0007
p0001 拖到 p0004 之后，通过计算（ p0004 ， p0005 ）的值，得到 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。