С# Сортировка списка при возврате исходных позиций индекса?

Мне интересно сортировать коллекцию, но также возвращать индекс, который можно использовать для сопоставления с исходной позицией в коллекции (до сортировки).

Позвольте мне привести более ясный пример:

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] ], для я = 0... 2

Есть ли в С#/.NET встроенный механизм, который упрощает его реализацию?

Спасибо.

Ответ 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], но, надеюсь, для вас это достаточно хорошо.

Ответ 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();   
}

Ответ 3

как-то более элегантный подход с использованием лямбда

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

это дает u idx массив из массива A