C# 给定所需的顺序需要一个节省空间的列表重新排序或排序

我的目标是：给定一个条目列表和所需的顺序，根据该顺序重新排列条目列表。该列表将非常大，因此空间效率很重要。

Ex:

List<Entry> data = ReadDataFromSomeWhere(); // data => [a, b, c];
List<int> ordering = RandomPermutation(data.Count); // ordering => [2, 1, 3];
data.ReOrderBy(ordering);  // data => [b, a, c];

我可能错了，但这似乎是最直接和最直接的节省空间解决方案是排序/排序data by the ordering。或者更一般地说：

给定两个列表：A，B 有没有办法按 B 对 A 进行排序？该功能本质上与以下相同：Array.Sort<(Of <(TKey, TValue>)>)(array<TKey>[]()[], array<TValue>[]()[])

我想到的一种方法是创建一个由 A 和 B 组成的新数据类型，即。配对，然后按 B 值排序：

List<T> A;
List<T> B;
Assert(A.Count == B.Count);
var C = A.Select( (a,idx) => new Pair<T,T>(B[idx],a)).OrderBy(c => c.First);
A = C.Select(x => x.Second).ToList();

但是，我希望尽可能节省空间（我猜 select 和 tolist() 调用都很昂贵），所以很大程度上就地排序是必要的。为此，有没有办法为 A.Sort() 编写一个引用 B 的比较器？

有两种解释顺序数组的方法，一种是列出每个元素的源索引，另一种是列出每个元素的目标索引。我不确定你指的是哪一个。

对给定目的地列表的列表进行重新排序非常简单：

// Sets list[destination[i]] = list[i] for all i.  Clobbers destination list.
void ReorderByDestination(List<T> list, List<int> destination) {
  for (int i = 0; i < list.Count; i++) {
    while (destination[i] != i) {
      int d = destination[i];
      T t = list[d];            // save element in destination slot
      int t_d = destination[d]; // and its own destination
      list[d] = list[i];        // move element to destination
      destination[d] = d;       // and mark it as moved
      list[i] = t;              // store saved element in slot i
      destination[i] = t_d;     // ... and its destination
    }
  }
}

给定源列表的列表重新排序（这就是我认为您想要的）有点困难，您只需要首先反转排列。

// Sets list[i] = list[source[i]] for all i.  Clobbers source list.
void ReorderBySource(List<T> list, List<int> source) {
  InvertPermutation(source);
  ReorderByDestination(list, source);
}

有已知的就地排列反转例程，我发现的第一个是 perm_inv inSUBSET http://orion.math.iastate.edu/burkardt/f_src/subset/subset.f90.

通常，您不需要反转排列，而是修改生成源列表的任何内容以生成目标列表。