C# - самый быстрый способ сортировки массива примитивов и отслеживания их показателей

Question

Мне нужно float[] быть отсортированным. И мне нужно знать, где старые индексы находятся в новом массиве. Вот почему я не могу использовать Array.Sort(); или что угодно. Поэтому я хотел бы написать функцию, которая сортирует массив для меня и запоминает, по какому индексу он принимает каждое значение:

float[] input  = new float[] {1.5, 2, 0, 0.4, -1, 96, -56, 8, -45};
// sort
float[] output; // {-56, -45, -1, 0, 0.4, 1.5, 2, 8, 96};
int[] indices; // {6, 8, 4, 2, 3, 0, 1, 7, 5};

Размер массивов будет около 500. Как мне подойти к этому? Какой алгоритм сортировки и т. Д.

---

После решения: Меня всегда удивляет, насколько мощным является C#. Я даже не думал, что смогу выполнить эту задачу самостоятельно. И так как я уже слышал, что Array.Sort() очень быстро возьму.

Answer 1

float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 };
int[] indices = new int[input.Length];
for (int i = 0; i < indices.Length; i++) indices[i] = i;
Array.Sort(input, indices);
// input and indices are now at the desired exit state

В основном, версия с двумя аргументами Array.Sort применяет одинаковые операции к обоим массивам, выполняя фактические сравнения сортировки в первом массиве. Обычно это используется наоборот - что-то переставлять по желаемым показателям; но это тоже работает.

Answer 2

Вы можете использовать перегрузку Array.Sort(), которая принимает ДВА массива и сортирует второй в соответствии с тем, как он отсортировал первый:

float[] input  = new [] { 1.5f, 2, 0, 0.4f, -1, 96, -56, 8, -45 };
int[] indices = Enumerable.Range(0, input.Length).ToArray();
Array.Sort(input, indices);

Answer 3

Вы можете создать новый массив индексов, а затем отсортировать их оба с помощью Array.Sort и обработки input в качестве ключей:

float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 };
int[] indicies = Enumerable.Range(0, input.Length).ToArray();
Array.Sort(input, indicies);

Answer 4

Если вы используете linq:

    float[] input = new float[] { 1.5F, 2, 0, 0.4F, -1, 96, -56, 8, -45 };

    var result = input.Select(x => new { Value = x, Index = input.ToList().IndexOf(x)}).OrderBy(x => x.Value).ToList();

    // sort
    float[] output = result.Select(x => x.Value).ToArray();
    int[] indices = result.Select(x => x.Index).ToArray();

в результате вы получили объекты со значениями и их индексами.

Answer 5

List<KeyValuePair<int,float>> и пользовательский сортировщик также будет работать. ключ для каждой пары содержит исходный индекс.

    private void Form1_Load(object sender, EventArgs e)
    {           
        List<KeyValuePair<int,float>> data = new List<KeyValuePair<int,float>>
        {
             new KeyValuePair<int,float>(0,1.5f),
             new KeyValuePair<int,float>(1,2),
             new KeyValuePair<int,float>(2,0),
             new KeyValuePair<int,float>(3,0.4f),
             new KeyValuePair<int,float>(4,-1),
             new KeyValuePair<int,float>(5,96),
             new KeyValuePair<int,float>(6,-56),
             new KeyValuePair<int,float>(7,8),
             new KeyValuePair<int,float>(8,-45)
        };
        data.Sort(SortByValue);
        foreach (KeyValuePair<int, float> kv in data)
        {
            listBox1.Items.Add(kv.Key.ToString() + " - " + kv.Value.ToString());
        }


    }
    private int SortByValue(KeyValuePair<int, float> a, KeyValuePair<int, float> b)
    {
        return a.Value.CompareTo(b.Value);
    }