基于数据连续性的排序

Question

假设有一类数据，如下面的伪代码。

class Data
    decimal Addition
    decimal Result
end

并且有一个数组或数据列表。例如：

[0] --> { Addition = 0.0, Result = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 }
[2] --> { Addition = 5.0, Result = 65.0 }
[3] --> { Addition = 30.0, Result = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 }

第一成员的结果应该等于第一成员的结果+第一成员的加法结果。在上面的示例中，顺序应该是0、1、3、4、2，如下所示：

[0] --> { Addition = 0.0, Result = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 }
[3] --> { Addition = 30.0, Result = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0 }

如果有两个或多个成员具有相同的结果，那么最早的数组成员将被排序。如何对这类数据进行O(N lg N)排序？

Answer 1

假设序列必须由值加法= 0.0的数据启动。通过查找每个数据的前一个值，我们可以发现

PreviousValue = Addition-Result

例如

[0] --> { Addition = 0.0, Result = 60.0, PreviousValue = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0, PreviousValue = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0, PreviousValue = 60.0 }
[3] --> { Addition = 30.0, Result = 80.0, PreviousValue = 50.0 }
[4] --> { Addition = -20.0, Result = 60.0, PreviousValue = 80.0 }

然后我们可以按照它的PreviousValue对这个列表进行排序，如下所示

[3] --> { Addition = 30.0, Result = 80.0, PreviousValue = 50.0 }
[0] --> { Addition = 0.0, Result = 60.0, PreviousValue = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0, PreviousValue = 60.0 }
[2] --> { Addition = 5.0, Result = 65.0, PreviousValue = 60.0 }
[4] --> { Addition = -20.0, Result = 60.0, PreviousValue = 80.0 }

然后，从初始节点(值加法= 0.0)开始，可以在排序列表上使用O(lg n)二进制搜索来查找下一个结果等于当前PreviousValue的序列的数据。因此，这个问题可以用O(n +2nlg n)的复杂度来解决。

Answer 2

数据本质上是一个图表。重写每个成员，以便：

[0] --> { Addition = 0.0, Result = 60.0 }   --> { From =  0.0, To = 60.0 }
[1] --> { Addition = -10.0, Result = 50.0 } --> { From = 60.0, To = 50.0 }
[2] --> { Addition = 5.0, Result = 65.0 }   --> { From = 60.0, To = 65.0 }
[3] --> { Addition = 30.0, Result = 80.0 }  --> { From = 50.0, To = 80.0 }
[4] --> { Addition = -20.0, Result = 60.0 } --> { From = 80.0, To = 60.0 }

使用值标记图节点，每个成员都是边。

现在去阅读图遍历算法和欧拉路径。