C# 排序列表同时还返回原始索引位置？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1760185/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C# Sort list while also returning the original index positions?
提问by homie347
I'm interested in sorting a collection, but also returning an index which can be used to map to the original position in the collection (before the sort).
我对排序集合感兴趣，但也返回一个索引，该索引可用于映射到集合中的原始位置（排序之前）。
Let me give an example to be more clear:
让我举个例子更清楚：
List<int> A = new List<int>(){3,2,1};
List<int> B;
List<int> idx;
Sort(A,out B,out idx);
After which:
之后：
A = [3,2,1]
B = [1,2,3]
idx = [2,1,0]
So that the relationship between A,B,idx is:
所以 A,B,idx 之间的关系是：
A[i] == B[ idx[i] ], for i = 0...2
A[i] == B[ idx[i] ], 对于 i = 0...2
Does C#/.Net have any built in mechanism to make this easy to implement?
C#/.Net 是否有任何内置机制可以轻松实现？
Thanks.
谢谢。
采纳答案by Mark Byers
It can be done quite easily using Linq.
使用 Linq 可以很容易地完成。
- Convert your list into a new list of pairs (object, original index of object).
- Sort the new list by the first item in the pair
- Extract the sorted list and the original indices.
- 将您的列表转换为新的对列表（对象，对象的原始索引）。
- 按对中的第一项对新列表进行排序
- 提取排序列表和原始索引。
Here's some code to demonstrate the principle:
下面是一些代码来演示原理：
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();
I think this gives A[idx[i]] = B[i], but that hopefully is good enough for you.
我认为这给出了 A[idx[i]] = B[i]，但希望这对你来说已经足够了。
回答by jason
While Mark Byers provided you a solutionusing LINQ, I want to show you another solution using the .NET Framework.
虽然 Mark Byers 为您提供了一个使用 LINQ的解决方案，但我想向您展示另一个使用 .NET Framework 的解决方案。
There is an overload of Array.Sortthat will do this for you:
有一个过载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 }));
Thus, here is a generic method meeting your specification that leverages this overload:
因此，这是一个利用此重载满足您的规范的通用方法：
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();
}
回答by Mohamed BenHaddou
a somehow more elegant approach using lambda
使用 lambda 的一种更优雅的方法
Array.Sort<int>(idx, (a, b) => A[a].CompareTo(A[b]));
this gives u idx array from the A array
这给了你来自 A 数组的 idx 数组
回答by Yeldar Kurmangaliyev
As for now, you can also utilize anonymous types or value tuples instead of KeyValuePair. It will provide more precise naming and make your code more readable:
至于现在，您还可以使用匿名类型或值元组而不是KeyValuePair. 它将提供更精确的命名并使您的代码更具可读性：
Anonymous types (C# 3.0):
匿名类型（C# 3.0）：
List<int> arr = new List<int>() { 3, 2, 1 };
var sorted = arr
.Select((x, i) => new { Value = x, OriginalIndex = i }))
.OrderBy(x => x.Value)
.ToList();
int originalIndexOfTheSmallestItem = sorted[0].OriginalIndex;
List<int> B = sorted.Select(x => x.Value).ToList();
List<int> idx = sorted.Select(x => x.OriginalIndex).ToList();
Value tuples (C# 7.0):
值元组 (C# 7.0)：
List<int> arr = new List<int>() { 3, 2, 1 };
var sorted = arr
.Select((x, i) => (Value: x, OriginalIndex: i))
.OrderBy(x => x.Value)
.ToList();
int originalIndexOfTheSmallestItem = sorted[0].OriginalIndex;
List<int> B = sorted.Select(x => x.Value).ToList();
List<int> idx = sorted.Select(x => x.OriginalIndex).ToList();
The difference is that you can return value tuple from your method and use it, but anonymous type can only be used within this method.
不同之处在于您可以从您的方法返回值元组并使用它，但匿名类型只能在此方法中使用。
