Создание массива с порядком чисел из другого массива

Question

Я ищу запись массива, который принимает значения другого массива и «сортирует» их в другой массив на основе их размера.

Пример:

массив [16, 5, 23, 1, 19]

бы в конечном итоге во втором массиве, как

[2, 1, 4, 0, 3 ]

Первый массив может быть любого размера, но предполагается, что в нем нет дубликатов. Он НЕ должен сортировать числа от наибольшего к самому большому, сохранение позиции в массиве жизненно важно.

Answer 1

Наивная реализация:

var array = new []{16, 5, 23, 1, 19}; 

var sortedArray = array.OrderBy(x=>x).ToArray(); 

var result = new int[array.Length]; 

for(int i = 0; i<result.Length; i++) 
    result[i] = Array.IndexOf(sortedArray, array[i]); 

Answer 2

var result = origArray.Select(Tuple.Create<int, int>) 
    .OrderBy(t => t.Item1) 
    .Select((t, x) => Tuple.Create(t.Item2, x)) 
    .OrderBy(s => s.Item1) 
    .Select(s => s.Item2) 
    .ToArray(); 

Непроверено, поэтому, вероятно, нуждается в некоторой корректировке, но идея должна быть в порядке.

Answer 3

Вы можете сделать это, используя the overload of Array.Sort(), который берет два массива и сортирует второй по заказу, который он сортирует первым.

var array = new[] { 16, 5, 23, 1, 19 }; 
var indices = Enumerable.Range(0, array.Length).ToArray(); 
Array.Sort(array.ToArray(), indices); 
var result = new int[array.Length]; 

for (int i = 0; i < result.Length; ++i) 
    result[indices[i]] = i; 

// Now result[] contains the answer. 

Это использует пару O(n) операций, чтобы сделать копию массива и создать indices массив в начале, а затем с помощью O(n log n) рода, и, наконец, заканчивает с O(n) операции переставить result[].

(алгоритмы, представленные в другие ответы, скорее всего, немного медленнее, но вы, вероятно, на самом деле не волнует, если вы уже определили эту функцию, чтобы требовать maxmimum скорость -., Который кажется маловероятным)