C#排序列表同时还返回原始索引位置？

Question

我有兴趣对一个集合进行排序,但也返回一个索引,该索引可用于映射到集合中的原始位置(排序之前).

让我举一个例子来说明一点:

List<int> A = new List<int>(){3,2,1};
List<int> B;
List<int> idx;

Sort(A,out B,out idx);

之后:

A = [3,2,1] 
B = [1,2,3]
idx = [2,1,0]

所以A,B,idx之间的关系是:

A[i] == B[ idx[i] ] ,因为i = 0 ... 2

C#/ .Net是否有任何内置机制使其易于实现？

谢谢.

Answer 1

使用Linq可以很容易地完成.

• 将列表转换为新的对列表(对象,对象的原始索引).
• 按对中的第一项对新列表进行排序
• 提取排序列表和原始索引.

这里有一些代码来演示原理:

List<int> A = new List<int>() { 3, 2, 1 };

var sorted = A
    .Select((x, i) => new KeyValuePair<int, int>(x, i))
    .OrderBy(x => x.Key)
    .ToList();

List<int> B = sorted.Select(x => x.Key).ToList();
List<int> idx = sorted.Select(x => x.Value).ToList();

我认为这给了A [idx [i]] = B [i],但希望这对你来说已经足够了.

Answer 2

虽然Mark Byers为您提供了使用LINQ 的解决方案,但我想向您展示使用.NET Framework的另一种解决方案.

有一个超载Array.Sort会为你做这件事:

int[] a = new[] { 3, 2, 1 };
int[] p = new[] { 0, 1, 2 };

Array.Sort(a, p);

Assert.IsTrue(a.SequenceEquals(new[] { 1, 2, 3 }));
Assert.IsTrue(p.SequenceEquals(new[] { 2, 1, 0 }));

因此,这是一个符合您的规范的通用方法,它利用了这个重载:

void Sort<T>(
    List<T> input,
    out List<T> output,
    out List<int> permutation,
    IComparer<T> comparer
) {
    if(input == null) { throw new ArgumentNullException("input"); }
    if(input.Count == 0) {
        // give back empty lists
        output = new List<T>(); 
        permutation = new List<int>();
        return;
    }
    if(comparer == null) { throw new ArgumentNullException("comparer"); }
    int[] items = Enumerable.Range(0, input.Count).ToArray();
    T[] keys = input.ToArray();
    Array.Sort(keys, items, comparer);
    output = keys.ToList();
    permutation = items.ToList();   
}

Answer 3

使用lambda以某种方式更优雅的方法

Array.Sort<int>(idx, (a, b) => A[a].CompareTo(A[b]));

这给出了A数组中的u idx数组