有序列表最优重排算法：基于参考项的位置调整方案

背景 #

现有存储物品信息的SQL表，数据如下：

id name  order
==============
1  book  3
2  table 1
3  chair 2
4  bag   4

当前物品的排序顺序为：

1. table
2. chair
3. book
4. bag

技术需求 #

用户可通过表单选择参考物品，并指定目标物品放置在参考物品的前/后位置来调整排序。需设计复杂度尽可能接近O(N)的最优重排算法，将物品的order值重新生成为1到N（N为物品总数），要求资源消耗最少。若可行，需提供伪代码或代码实现。

调整示例 #

基于上述数据集，以下是不同调整操作后的结果：

案例1：将bag放置在table之前 #

id name  order
==============
1  book  4
2  table 2
3  chair 3
4  bag   1

案例2：基于案例1结果，将table放置在chair之后 #

id name  order
==============
1  book  4
2  table 3
3  chair 2
4  bag   1

案例3：基于案例2结果，将book放置在chair之前 #

id name  order
==============
1  book  2
2  table 4
3  chair 3
4  bag   1

案例4：基于案例3结果，将bag放置在chair之前 #

id name  order
==============
1  book  1
2  table 4
3  chair 3
4  bag   2

内容的提问来源于stack exchange，提问作者Anwar