algorithm - 排序算法以保持排序位置编号更新

Question

每隔一段时间，我必须处理用户可以手动排序的元素列表。

在大多数情况下，我尝试依赖使用顺序敏感容器的模型，但这并不总是可行的，因此我不得不向我的数据添加位置字段。这个位置字段是 double 类型，因此我总能计算出两个数字之间的位置。然而，这并不理想，因为我担心会遇到边缘情况，在这种情况下我没有足够的数值精度来继续在两个数字之间插入。

我对维持职位编号的最佳方法存疑。第一个想法是遍历所有行并在每次插入后给它们一个整数，例如:

在 2 和 3 之间放下一行之后:

1   2   2.5   3   4    5

位置编号更新后:

1   2   3     4   5    6

当然，如果我有大量条目，那可能会变得很重。不是特别在内存中，而是将所有新值存储回磁盘/数据库。我通常使用某种类型的 ORM 和移动软件。更新所有代码将从磁盘中提取每个对象并将它们设置为脏，导致重新验证我的数据模型的所有相关验证规则。

我也可以等到精度不足以计算两个位置之间的数字。然而，用户体验会很差，因为相同的操作将不再需要相同的时间。

我相信针对这些情况有一种标准算法可以定期且持续地更新位置编号，或者只是其中的一些。理想情况下它应该是 O(log n)，最坏情况和最好情况之间没有大的时间差异。

老实说，我也认为任何必须由用户/排序的东西，在最坏的情况下都不能大到成为真正的问题。边缘情况似乎也极为罕见，如果我搜索插入边界数字的解决方案，则情况会更加罕见。但是我仍然相信对于这个问题有一个标准的众所周知的解决方案，我不知道，我想了解它。

Answer 1

第二次尝试。

考虑整个 position 值范围，比如 0 -> 1000

我们插入的第一个项目的位置应该是 500。我们的列表现在是:

(0) -> 500 -> (1000).

如果你在第一个位置插入另一个项目，我们最终会得到:

(0) -> 250 -> 500 -> (1000).

如果我们一直在第一个位置插入项目，我们就会遇到问题，因为我们的范围不平衡并且...等等...平衡？听起来不像binary tree吗？问题!？

基本上，您将列表存储为二叉树。插入节点时，根据周围节点为其分配位置。当你的树变得不平衡时，你旋转节点使其再次平衡并重新计算旋转节点的位置!

所以:

• 大多数时候，添加一个节点不需要改变其他节点的位置。
• 当需要平衡时，只会更改部分项目。
• O(log n) !

编辑