问具有order属性的对象重新排序

EN

使用浮点数进行排序

对于push，给对象分配一个与现在索引1减去1 (list[0].order = list[1].order - 1)的对象的顺序相等的顺序

对于swap，交换两个对象的顺序(temp = list[i]; list[i] = list[j]; list[j] = list[i]; temp = list[i].order; list[i].order = list[j].order; list[j].order = temp)；如果这可能导致一致性问题，那么理想情况下，您可以在元素上放置一个transit标志，以指示它们的顺序正在被修改，或者在最坏的情况下锁定对象直到它们是一致的。

对于remove，什么都不做--列表中的对象仍然是有序的，您刚刚在序列中引入了一个空白，这不应该是一个问题

insert是唯一有问题的。如果要在索引i处插入元素，则其顺序等于索引i-1和i+1 (list[i].order = (list[i-1].order + list[i+1].order)/2)中元素顺序的平均值。验证此新订单不等于索引i-1或i+1 (list[i].order != list[i-1].order && list[i].order != list[i+1].order)中的顺序--这表示您已经命中了计算机epsilon。当发生这种情况时(而且这种情况很少发生)，您有两个选项：

1. 咬紧牙关，重新排序整个列表，即在索引0处指定0顺序，在索引1处指定1顺序，指数n处的A阶n。
2. 进行一次本地重新订购，以尽量减少成本。在重新排序list[i-1].order = (list[i-2].order + list[i-1].order)/2和list[i+1].order = (list[i+2].order + list[i+1].order)/2之前，将相邻的元素重新排序到list[i] = (list[i-1] + list[i+1])/2，再次验证您还没有到达i-1处的机器表观子和i+1重新排序--如果您已经到达机器epsilon (例如i-1 )，然后先将i-2重新排序到list[i-2].order = (list[i-3].order + list[i-2].order)/2，然后再重新排序i-1。如果i-2重新排序击中机器epsilon，那么首先重新排序i-3，依此类推.(如果您到达列表的末尾，那么只需减少元素的顺序或增加元素n的顺序。)正如您所看到的，在最坏的情况下，您已经得到了一个比简单地咬紧牙关重新排序整个列表更昂贵的级联重新排序；但是，很可能重新排序仍然是本地的。一个很好的折衷方法是，如果你已经级联了太多次(对于合理的值“太多”)，那么做一个完整的重新排序。

为了把它扔出去，一个双链接的列表给了你：

• push(object)：O(1)，给它比当前磁头少1的订单。
• swap(indexN, indexM)：O(n)，交换订单
• remove(object)：O(1)，不要碰任何命令
• insert(object)：O(n)，插入顺序，使列表按顺序排序

可能不是很好，因为第二个最重要的操作是昂贵的(更改订单)操作。