我的目标是：给定条目的列表，以及所希望的顺序，重新排列根据本订购条目列表。该列表将是非常大的，所以空间效率是重要的。

My objective is: Given a list of entries, and a desired ordering, rearrange the list of entries according to this ordering. The list will be very large, so space efficiency is important.

例如：

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];

我可能是错误的，但它似乎是最直接和节省空间的解决办法是进行排序/排序依据的的数据的通过的序的。或更一般

I may be mistaken, but it seems like the most straightforward and space efficient solution is to sort/orderby the data by the ordering. or more generally:

由于两个列表：A，B有没有办法用B来排序？的功能将是基本相同： 的Array.Sort≤（中≤（TKEY的，TValue＆GT;）＆GT;）（阵列＆LT; TKEY的＆GT; []（）[]数组＆LT; TValue＆GT; []（）[]）

Given two lists: A,B is there a way to sort A by B? The functionality would be essentially the same as: Array.Sort<(Of <(TKey, TValue>)>)(array<TKey>[]()[], array<TValue>[]()[])

这所想到的一个方法是创建一个由A和B，即组成一个新的数据类型。对，然后进行排序的B值：

One methodology that comes to mind is to create a new datatype which is composed from A and B, ie. Pair, then sort by the B values:

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();

不过，我想这是因为空间高效地（的两个选择的和了ToList（）调用我猜是昂贵的的），所以基本上就地排序是必要的。为此，有没有办法写一个比较器的A.Sort（），它引用B'

However, I would like this to be as space efficient as possible (both select's and the tolist() call I'm guessing are expensive), so a largely in-place sort is necessary. To this end, is there a way to write a comparer for A.Sort(), which references B?

推荐答案

有两种方法可以跨preT的顺序排列，其中一个是列出源索引每一个元素，而它在其中列出了对于每个元素目的地索引。我不知道哪一个你的意思。

There are two ways to interpret the order array, one in which it lists the source index for each element, and one in which it lists the destination index for each element. I'm not sure which one you mean.

重新排列给出的目的地列表清单是pretty的方便：

Reordering a list given a list of destinations is pretty easy:

// 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
    }
  }
}

重新排序给源列表（这是我认为你打算）的列表是有点困难，你只需要第一反转置换。

Reordering a list given a list of sources (which is what I think you're intending) is a bit harder, you just need to invert the permutation first.

// 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中的子集。

There are known in-place permutation inversion routines, the first one I found was perm_inv in SUBSET.

通常，不需要反转置换，而不是修改任何产生的源列表，以产生一个目的地列表，而不是

Often, you don't need to invert the permutation, instead modify whatever generated the source list to generate a destination list instead.