>我有一个对象
class Junction {
private String name;
private String previous;
private String next;
}
现在这些交汇点具有以下格式
Junction[name="T1H", previous="T0F", next="T345"]
Junction[name="K109", previous="TRH", next="JHD"]
Junction[name="LM89", previous="T1H", next="D679"]
Junction[name="TRH", previous="LM89", next="T345"]
以上将按顺序排序:
T1H->LM89->TRH->K109
但是,如果我有一个无序列表,我该如何对其进行排序?Java中最好的算法是什么。快速排序不起作用,因为枢轴和更高和更低的概念并不真正适用。您无法计算出某些内容是否更高,因为交汇点都是链接的。
气泡排序似乎是合乎逻辑的。
有什么想法吗?
您可以使用哈希映射来存储每个交汇点的后续交汇点,使用这些交汇点previous
属性。 如果"上一个"交汇点不在列表中,则使用 None
、 null
或任何其他特殊值。这假设所有交汇点都是直接后继交汇点或其他交汇点,并且没有两个交汇点具有相同的"前一个"交汇点。对于 n 个结,复杂度将为 O(n(。
from collections import namedtuple
Junction = namedtuple("Junction", "name previous next")
junctions = [
Junction(name="T1H", previous="T0F", next="T345"),
Junction(name="K109", previous="TRH", next="JHD"),
Junction(name="LM89", previous="T1H", next="D679"),
Junction(name="TRH", previous="LM89", next="T345")
]
d = {j.name: j for j in junctions} # map names to junctions
succ = {j: None for j in junctions} # map previous to successor
for j in junctions:
p = d.get(j.previous, None)
succ[p] = j
然后,从作为None
后继的交汇点开始,迭代所有交汇点:
j = succ[None]
while j:
print(j)
j = succ[j]
输出:
Junction(name='T1H', previous='T0F', next='T345')
Junction(name='LM89', previous='T1H', next='D679')
Junction(name='TRH', previous='LM89', next='T345')
Junction(name='K109', previous='TRH', next='JHD')
(在这里使用Python,因为你没有专门要求Java解决方案,但当然同样的事情可以很容易地在Java中完成。