c# - 在 C# 中，我如何按哪个项目更大来对这个对象列表进行排序？

Question

我有一个名为 Team 的简单类，它看起来像这样:

public class Team
{
     public Team ParentTeam;
     public string Name;
}

所以它有一个名称和对另一个团队的引用，即它的父团队。

我现在有一个从函数中返回的团队列表

List<Team> list = GetTeamsList();

给定一些假设:

1. 除一个(顶级团队)外，所有团队都有一个 ParentTeam
2. 列表中返回的每个团队都是同一层次结构的一部分，并且只有一个层次结构(没有 2 个团队处于同一“级别”)

我现在需要获取此函数的结果并按层次结构对列表进行排序

假设我们有以下团队信息:

|| Team Name || Parent Team Name ||
||-----------||------------------||   
|| Team A    || Team B           ||   
|| Team B    || Team C           ||   
|| Team C    || Team D           ||   
|| Team D    || null             || 

但 GetTeamsList() 函数以任意随机顺序返回团队。例如，它可能会返回列表:

 var teamA = GetTeamA();
 var teamB = GetTeamB();
 var teamC = GetTeamC();
 var teamD = GetTeamD();

 List<Team> list = new List() { teamD, teamA, teamB, teamC };

我需要重新排序这个列表，使其看起来像这样:

 List<Team> list = new List() { teamA, teamB, teamC, teamD };

我如何根据团队层次结构将列表重新排序为“正确”的顺序？

Answer 1

到目前为止给出的几个解决方案是正确的，而且所有的解决方案都至少是团队数量的二次方；随着团队数量的增加，它们将变得低效。

这里有一个解决方案，它 (1) 线性，(2) 更短，(3) 比目前的其他一些解决方案更容易理解:

static IEnumerable<Team> SortTeams(IEnumerable<Team> teams)
{
  var lookup = teams.ToDictionary(t => t.ParentTeam ?? new Team());
  var current = teams.Single(t => t.ParentTeam == null);
  do
    yield return current;
  while (lookup.TryGetValue(current, out current));
}

这会产生与您想要的顺序相反的序列，因此如果您希望它以其他顺序出现，请在调用末尾放置一个 Reverse:

Console.WriteLine(String.Join(" ", SortTeams(teams).Reverse().Select(t => t.Name)));

“虚拟”团队在那里，因为字典不允许键为空。