这是一个创建于 1652 天前的主题，其中的信息可能已经有所发展或是发生改变。
记得以前设计 CMS 系统的时候接触过这个问题，
文章表加一个 sort，然后让用户自己填写 sort 值，越大就越靠前，再加个 id 排序解决同样 sort 值问题，这种很适合翻页排序（特别是翻页后不显示其他页内容），但需要用户自己填写数值感觉不太友好。
后来出现了“拖拽排序”的交互，这种填值方式就走不通了，置顶和置尾还可以前端自动填值，中间的移动就没办法了，除非移动后把后面所有文章的 sort 值都 update 一次，少量文章还可以，量大了而且还可能涉及到多人同时操作的话，要不得。
寻求过其他方法，很多都说用“除二法”， 就是每个文章排序号中间有间距（ 100 和 200)，每往中间拖一个，sort 值就改为前后间距的二分一(150)，如此类推，一直除下去将会是浮点数。 且不说浮点数精准度会不会出现问题，乍看这个方案貌似有“次数限制”，如果不停地往“某个中间”拖入一个，浮点数的长度就是限制？后来想到一个法子规避这个次数限制，用定时任务方法定期优化一下排序数字，这算是个可行但很难的方案吧~~~
现在又遇到一个类似的开发需求，想咨询一下 2020 年了有无更好的解决方案？
 |
1
weixiangzhe 2020-05-27 15:32:10 +08:00
那不用数字成不成
1. 原始序号是 1,2,3,4,5 2. ‘5’拉到 1,2 之间变为 1@1 3. ‘4’再到 1,2 之间变为 1@2 4. ‘3’ 再拉到'1','2'之间为 1@1@1 5. 最后再按 @分割排序 |
 |
2
keepeye 2020-05-27 15:40:13 +08:00
其实也不用更新太多吧？一页能有几条数据，只要更新两个位置中间的行就可以了
|
 |
3
Shy07 2020-05-27 16:07:08 +08:00
文章 id 单独保存一个排序数组，简单暴力
|
 |
4
flipped598 2020-05-27 16:14:56 +08:00
同意二楼所说的，不用更新后边全部的，只更新两个位置中间所说的就行了，一页也没有多少数据。我们系统的后台就有这样的需求，由于基本上没有并发操作，目前也是这么实现的。
|
 |
5
star7th 2020-05-27 16:35:14 +08:00
我还真的是这么做的，不觉得有什么问题。我在 showdoc 的实现排序机制有两种，github.com/star7th/showdoc ，一种是用户操作后，就把目录 /页面的数字排序都更新一遍。一种是项目排序，简单地保存整个数组，然后读取的时候，在代码里根据这个数组进行重排。目前没遇到啥问题。你上面考虑的性能问题，算法问题，我觉得是多虑了的。不会有那么多人并发操作，也不会 update 得特别慢。就这么简单处理就好。
|
 |
6
fancy2020 2020-05-27 16:48:44 +08:00
正好现在做的项目<橙子简历> https://wonderfulcv.com 在编辑简历的部分有拖拽排序的功能，我是单独用一张表存储排序 id，数据量不大的话这样做比较省心
|
 |
7
damngood 2020-05-27 16:53:36 +08:00 via iPhone
我一般是用 double
|
 |
8
index90 2020-05-27 17:08:38 +08:00
你拖拽的跨度有多大？
假设你一个页面有一百条数据，那么每次拖拽用交换排序，最多更新一百条数据的索引值。 |
 |
9
yc8332 2020-05-27 17:28:07 +08:00
如果都有排序，其实只要更新交换的两个而已，如果没有排序或者有些值是一样的，那可能会多更新几个。。。这个我做过
|
 |
10
SakuraKuma 2020-05-27 17:33:13 +08:00
拖拽排序问题不大, 对比原序号和新序号 patch 一下就好, 现系统就是这么搞的.
问题是跨分页排序, 不分页嘛, 数据太多, 分页嘛, 跨分页拖拽不了. 有大佬提供下好思路嘛~ |
 |
11
lookas2001 2020-05-27 17:38:57 +08:00
实现一个序列，支持 O(logn)插入、删除（类似文字编辑器），典型的算法题啊，用平衡树，即使在最坏情况下也能保证时间。
不过我觉得一般情况下，你最后提出的解决方案已经能很好的解决问题了，码量也不大。 |
|
12
lookas2001 2020-05-27 17:42:13 +08:00
平衡树也有实现，如果使用 js，可以看看这个库 https://github.com/mourner/bbtree
|
 |
13
hronro 2020-05-27 17:45:24 +08:00 via iPhone
@lookas2001 问的是储存方案，最后应该是要和数据库挂钩的
|
 |
14
raysonlu OP |
|
15
raysonlu OP |
|
16
raysonlu OP @lookas2001 定时器方案确实能解决，但这的确太奇葩，我思考着我以后项目交接接手人看到这个定时任务会一脸懵逼，毕竟我刚在小组提出这个问题，几乎全部人一来就表示“这不是很简单吗”。平衡树我也有用来解决过一些需求，但这里无法应用啊，毕竟基本场景是数据库查表。
@hronro 当然如果有其他曲线方案能解决也比较好，比如数据库纯天然般支持这种排序需求 |
|
17
fancy2020 2020-05-27 18:12:50 +08:00 via iPhone
@raysonlu 我的回复里说过了，我的数据量不大所以才这样做，我需要排序的数据只有个位数(每个简历里的教育经历等的排序)。十万这种的肯定就需要其他方案了
|
 |
18
DavidNineRoc 2020-05-27 19:01:32 +08:00
数据量大要处理的问题:
加入排序位置是 1 10 100 100 1. 把第三位放到第一位的处理方案 2. 之后把末尾放到第一位的解决方案 3. 重复以上两个步骤一百次. |
|
19
DavidNineRoc 2020-05-27 19:02:39 +08:00
如果对于用户级别的排序没有分页可以考虑使用双链表, 全部的排序另说
|
|
20
index90 2020-05-27 19:08:36 +08:00
@raysonlu 怎么会呢？
假设你当前页有十条数据，你现在把第 7 条数据拖到第 4 条数据前，那么需要变更的数据有 D，E，F，G： 1 A--A 2 B--B 3 C--C 4 D--G 5 E--D 6 F--E 7 G--F 8 H--H 9 I--I 10 J--J 所以结合场景，如果你一页所展示的数据大小为 100 条数据，那么最坏的情况下，你要变更 100 条数据，无论你的总量是多少。 但如果你支持跨页拖拽，你就当我没说。 |
 |
21
sarvatathagata 2020-05-27 19:15:21 +08:00
作为一个 OIer，一般用替罪羊树做动态标号就行了。
|
 |
22
Akkuman 2020-05-27 19:28:21 +08:00 via Android
100/(2^1000)=9.3326362e-300
DOUBLE——一个双精度浮点数。支持 -1.7976931348623157E+308 到-2.2250738585072014E-308，0 和 2.2250738585072014E- 308 到 1.7976931348623157E+308 。如果是 FLOAT，UNSIGNED 不会改变正数范围，但负数是不允许的。 • DOUBLE PRECISION——同 DOUBLE • REAL——同 DOUBLE • DECIMAL——将一个数像字符串那样存储，每个字符占一个字节 • DEC——同 DECIMAL • NUMERIC——同 DECIMAL 也就是说，你往同一个地方不停地得拖动一千多次，才会出现次数限制，现实场景好像并不多，如果担心可以用 decimal |
|
23
index90 2020-05-27 19:32:24 +08:00
？？？
是我理解错题目了？ 难道不是在一个 10W 个元素的数组中，把第 10 个元素移动到第 5 个元素的位置吗？那么只要重排 5~10 位置上的元素就可以啦。跟第 11，12，13，第 10 万的元素有什么关系呢？时间复杂度就是元素移动的距离。 好像还有置顶和置尾功能？用标记就好啦，查询的时候用 where 过滤一下。 越看评论越觉得我弱智了，是我理解错了吗？ |
 |
24
agagega 2020-05-27 19:38:19 +08:00
别用浮点数，用字符串。A 和 B 中间的，就是 AA
|
|
25
Shy07 2020-05-27 21:03:30 +08:00
@raysonlu
我说的文章 id 单独保存一个排序数组是指：id 1~5 的文章就单独保存一个 [1...5] 的数组 a 分页显示 [1, 2, 3] ，排序后是 [3, 2, 1] 的话，就更新数组 a page 和 pageSize 范围内的值。 这样的好处是不用修改文章数据，你在排序的时候，别人也可以编辑文章内容；同时文章本身是如何存储的、顺序如何数组 a 完全不 care. |
 |
26
px920906 2020-05-27 21:45:55 +08:00  1
之前正好也搜过相关的方案，teambition 就是“除二法”，每次请求后都检查一遍，不满足相邻最小差值就重新计算并返回新的值给前端 -> https://www.zhihu.com/question/55789722/answer/146650607
（回答好像写错了吧 |
|
27
raysonlu OP @index90 不好意思，我那个举例的确有一些问题，如你所说“时间复杂度就是元素移动的距离”是正确的，但我初衷也是想解决这个问题。
也的确要“支持跨页拖拽”，按我的理解，出现了“拖拽”这个交互后，仅仅显示一页的内容让用户拖拽排序是没意义的吧（比如把下一页的第一个拖拽到这一页中间），这时候一般做下拉式分页展示，也因此，跨度距离就变得不可控（想象中的交互场景：用户抓起某个文章，移动到靠上(下)的位置，页面不停往上(下)滚动，然后找到位置放下） |
 |
28
mazhan465 2020-05-28 10:20:39 +08:00
为啥不用链表呢，或者跳表？
|
|
30
mazhan465 2020-05-28 11:07:56 +08:00
@raysonlu 表加个 next 字段，保存下个节点的 id，比如当前顺序 1,2,3,4,5，将 5 拖到 2,3 之间，查 next=3 的改为 next=5,next=5 的改为 5 的 next，也就是 NULL 或者 0
|
|
32
raysonlu OP @mazhan465 #13 是啊，分页排序本是类似“把数据全倒出来”的活儿，只是数据库的 order 帮我们优美地干了，但这种链表的方案，就只能做在业务代码层了，这就”真·全倒出来“了~
|
 |
34
no1xsyzy 2020-05-28 13:44:39 +08:00
不太确定还需要何种访问方式，盲狙一个 B-tree
|
|
36
no1xsyzy 2020-05-28 18:34:27 +08:00
@raysonlu #35 做一张表来实现，表的一行代表 B-tree 的一个节点，用 id 来引用
其实各种树都可以这么玩，只不过访问数据库次数比较关键，选访问次数比较低的树吧，宽度比较大的 B-tree 会比较好。 只不过 “给定项目，获知其在第几个位置” 的查询比较麻烦 更加元分析地：一维数组，处理序相关问题基本就是树和桶，访问次数低的就是 B-tree 和 “二除法”。 盲狙一个 B-tree 没错的，不过也就是盲狙，并没有相应场景的实际的演练。 桶其实大部分情况下可以用了，遇到极限情况进行重建就行。就算是定时任务，做好注释问题不大。 如果不能满足要求那就是树了。 也可能不是你自己实现，采用数据库内已经是树方式实现的索引方式也是可以的，访问次数也很低。 |
Select Language