按另一个内存列表对内存列表排序

Question

是否可以按另一个列表(第二个列表将是引用数据源或类似的东西)对内存中的列表进行排序?

public class DataItem
{
    public string Name { get; set; }
    public string Path { get; set; }
}
// a list of Data Items, randomly sorted
List<DataItem> dataItems = GetDataItems();
// the sort order data source with the paths in the correct order
IEnumerable<string> sortOrder = new List<string> {
    "A",
    "A.A1",
    "A.A2",
    "A.B1"
};
// is there a way to tell linq to sort the in-memory list of objects
// by the sortOrder "data source"
dataItems = dataItems.OrderBy(p => p.Path == sortOrder).ToList();

Answer 1

首先，让我们为sortOrder中的每个项分配一个索引:

var sortOrderWithIndices = sortOrder.Select((x, i) => new { path = x, index = i });

接下来，我们连接两个列表并排序:

var dataItemsOrdered =
 from d in dataItems
 join x in sortOrderWithIndices on d.Path equals x.path //pull index by path
 orderby x.index //order by index
 select d;

Answer 2

这里有一种替代方法(我认为更有效)作为被接受的答案。

List<DataItem> dataItems = GetDataItems();
IDictionary<string, int> sortOrder = new Dictionary<string, int>()
{
     {"A", int.MaxValue},
     {"A.A1", int.MaxValue-1},
     {"A.A2", int.MaxValue -2},
     {"A.B1", int.MaxValue-3},
};
dataItems.Sort((di1, di2) => sortOrder[di1.Path].CompareTo(sortOrder[di2.Path]));

设Sort()和OrderBy()均取O(n*logn)，其中n为dataItems中的项数。这里给出的解决方案需要O(n*logn)来执行排序。我们假设创建字典sortOrder所需的步骤的成本与原始文章中创建字典IEnumerable的成本没有显著差异。

执行join和然后对集合进行排序，但是增加了额外的成本O(nm)，其中m是sortOrder中的元素数。因此，该解的总时间复杂度为O(nm + nlogn)。

理论上，使用join的方法可以归结为O(n* (m + logn)) ~= O(n*logn)。但在实践中，join需要额外的周期。这是在linq方法中可能产生的额外空间复杂性之外的，为了处理linq查询，可能已经创建了辅助集合。

Answer 3

如果您的路径列表很大，您最好使用字典执行查找:

var sortValues = sortOrder.Select((p, i) => new { Path = p, Value = i })
                          .ToDictionary(x => x.Path, x => x.Value);
dataItems = dataItems.OrderBy(di => sortValues[di.Path]).ToList();

Answer 4

自定义排序是通过使用自定义比较器(IComparer接口的实现)来完成的，该比较器作为OrderBy方法的第二个参数传递。