常见问题，排序值的插入以及对排序值的维护

我们常常会遇到排序的需求。给列表的每一行一个排序值，如0-100，然后列表展示根据这个排序值来排序。排序值的变更我遇到的有2种：
1、交换值（即两个行的排序值交换，影响两行，如第一行和第三行交换排序值。）
2、移动值（即移动值的前后位置，被影响的行数量取决于插入的位置，离开的位置和表的数据量。如第四行插入到第二行，则第二行到第四行的排序值都需要做出改变）。
3、插值（即插入一个随机值，所插值后面的顺序都会受到影响）

复杂度

用时间复杂度来估算：
1、交换值的时间复杂度就是O(2)，也可以记作O(1)。
2、插值的复杂度则是O(N)，有点类似线性表的顺序表的操作。
下面是有关线性表的简单介绍：
https://blog.dugwang.com/?p=1158

交换值

1、交换值的实现较为简单，如1和3交换，我们只需引入一个临时变量来存储要变更的其中一个值就行了

        $a = [1,2,3];
        $b = $a[0];
        $a[0] = $a[2];
        $a[2] = $b;

移动值

我们先复习下线性表的顺序表是怎么做插入操作的：

顺序表的插入：因为是顺序存储，新插入的数据占位，那么插入数据后面的数据都要向后移动一位。
顺序表的删除：同样，新删除的数据不占位，那么删除数据后面的数据都要向前移动一位。

我们的移动值其实就是相当于同时执行了顺序表的删除和插入两个操作。

假设我们现在有个表格：

image.png
例一：将排序值从2设为4的位置执行顺序如图： image.png

例二：将排序值从4设为2的位置执行顺序如图：

image.png

黄色背景的是变更的值，橙色背景的是受影响的排序值。

执行顺序
1：我们先将黄色的排序值修改，如例一将2改成4，例二将4改成2
2：然后确定受影响的值的范围
2.1：根据例一可得：增加排序值的影响范围是大于当前排序值，小于等于要修改到的排序值（如例一排序值大于4且小于等于2的排序值为序号3和序号4）
2.2：根据例二可得：减少排序值的影响范围是大于等于要修改到的排序值，小于当前的排序值（如例二排序值大于等于2且小于4的排序值为序号2和序号3）
3：最后确定受影响值的增减
3.1：根据例一可得，增加排序值，则受影响的其他排序值需要减一
3.2：根据例二可得，减少排序值，则受影响的其他排序值需要加一

以MySQL为例

以Mysql为例，有表结构如下：

id  sort_num
1   1
2   2
3   3
4   4

增加排序值：以例一为例，我们把id为2的排序值改成4：

我们可以先执行

update table set sort_num=4 where id = 2;
再执行：
update table set sort_num=sort_num-1 where sort_num>2 and sort_num <= 4;

执行结果：

id  sort_num
1   1
2   4
3   2
4   3

减少排序值：以例二为例，还用上面的那个表，我们把id为4的排序值改成2：

我们可以先执行

update table set sort_num=2 where id = 4;
再执行：
update table set sort_num=sort_num+1 where sort_num>=2 and sort_num < 4;

执行结果：

id  sort_num
1   1
2   3
3   4
4   2

可以看到，id为2和以后的数据，除了5，sort_num都增加了1。

删除数据时对排序值的维护

删除后就把删除的排序值之后的所有排序值减一就可以了。

后续

从数据结构来看，现在的排序值是线性表，而且是顺序表。所以修改时，要变更的值比较多。
而在数据结构上，线性表后面就是链表，可以更快速的变更排序值。映射到实际应用中，就是左右值。比如我们常见的递归取父节点，可以在数据表中增加left和right字段，利用链表的特性，快速找到指定节点的子节点和父节点。
而我们实际应用中，各种数据结构在不同的场景中各有优势，能根据实际需求去确定要使用的结构，也是对一个人的考验。
enjoy it!