Как отсортировать по возрастанию только нечетные числа в массиве?

Question

Я хочу отсортировать только нечетные числа без перемещения четных чисел. Например, если мой ввод:

[5, 3, 2, 8, 1, 4]

Ожидаемый результат:

[1, 3, 2, 8, 5, 4]

Я новичок в C #, и я столкнулся с проблемой в Интернете, которая озадачила меня. Я пытался часами, и я хотел бы изучить эту концепцию в

Состояния вызова:

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

Вот мой код, пожалуйста, успокойтесь, я на начальных этапах программирования.

public static int[] SortArray(int[] array)
{
    var dict = new Dictionary<int, int>();
    var dict2 = new Dictionary<int, int>();

    for (int i = 0; i < array.Length; i++)
    {
        int j =0;
        if (array[i] % 2 != 0)
        {
            dict.Add(array[i], i+1);
        }
        else
        {
            dict2.Add(array[i], i+1);
        }
    }
    var result = dict.OrderBy(x => x.Key);
    Dictionary<int, int> resultDic = result.Union(dict2)
      .GroupBy(x => x.Key).ToDictionary(o => o.Key, o => o.Key);
}

public static void Main()
{
    SortArray(new int[] { 5, 3, 2, 8, 1, 4});
}

Answer 1

Вы можете сделать это с помощью linq, проиндексировав числа перед началом:

var nums = new[] { 5, 3, 2, 8, 1, 4 };
var indexedNums = nums.Select((num, idx) => new { num, idx }).ToList();

Затем сортируем эти проиндексированные числа по четности и коэффициентам:

var evens = indexedNums.Where(x => x.num % 2 == 0);
var odds = indexedNums.Where(x => x.num % 2 == 1);

Сортировка нечетных (проиндексированных) чисел по их значению:

var sortedOdds = odds.OrderBy(x => x.num); //sort the odd numbers by their value

Сжатие этой последовательности с последовательностью odds (которая отсортирована по индексу), взяв число из sortedOdds и индекс из odds

var reindexedOdds = sortedOdds.Zip(odds, (o1, o2) => new { o1.num, o2.idx });

... и выбрасываем эти reindexedOdds в последовательность с индексом evens сверху, сортируем по индексу и затем выбираем число.

var endSequence = evens.Concat(reindexedOdds).OrderBy(x => x.idx).Select(x => x.num);

Answer 2

Хотя другие решения формально верны, большинство из них неэффективны, поскольку имеют O(n^2) сложность времени.

Другой (и более эффективный по времени) подход должен подразумевать использование двух списков: первый будет содержать индексы нечетных чисел, а второй будет хранить отсортированные нечетные числа.

public static int[] SortArray(int[] array)
{
    var sortedOdds = new List<int>(array.Length);
    var oddsIndexes = new List<int>(array.Length);
    var newArray = new int[array.Length];

    for(var i = 0; i < array.Length; i++) // O(n)
    {
        var value = array[i];
        if(value % 2 == 1)
        {
            sortedOdds.Add(value);
            oddsIndexes.Add(i);
        } else
        {
            newArray[i] = value;
        }
    }

    sortedOdds.Sort(); // average complexity O(n log n)

    for(var j = 0; j < sortedOdds.Count; j++) // O(n)
    {
        var value = sortedOdds[j];
        var index = oddsIndexes[j];
        newArray[index] = value;
    }

    return newArray;
}

Это снизит сложность в среднем до O(n log n) времени.

Answer 3

Проверьте этот код. Пояснения добавлены как комментарии

public static int[] SortArray(int[] array)
{
    //temp variable for holding larger value for switching
    int temp = 0;

    for (int i = 0; i < array.Length; i++)
    {
        //If the value is 'even' continue with outer loop
        if(array[i] % 2 == 0)
           continue;

        //Inner loop to compare array values
        for(int j = (i + 1); j < array.Length; j++)
        {
            //If this value is not even do comparison
            if(array[j] % 2 != 0)
            {
                //If the left value is greater than the right value
                //swap them
                if(array[i] > array[j])
                {
                   temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
                }
            }
        }
    }

    return array;
}

public static void Main()
{
    SortArray(new int[] { 5, 3, 2, 8, 1, 4});
}