Дан массив, состоящий из четных и нечетных чисел.Сортируйте массив сначала по четным, а затем по коэффициентам.Порядок номеров не может быть изменен

Question

Если входной массив равен - 1,4,3,8,6,5,7, вывод должен быть - 4 8 6 1 3 5 7

У меня есть одно решение с возможностью вставки,

void sortarrayinorder(int arr[],int size)
{
     int i,j,tem,k;
     for(i=1;i<size;i++)
     {
       for(j=0;j<i;j++)
       {
       if((arr[j]%2)!=0 && (arr[i]%2)==0)
       {
         tem=arr[j];
         arr[j]=arr[i];
         for(k =i;k>j;k--)
           arr[k]=arr[k-1];

           arr[k+1]=tem;
           }
         }
     }     
}

Можно ли решить эту проблему лучше?Сложность моего решения o (n2).Пожалуйста, предоставьте решение с меньшей временной сложностью.Дополнительное пространство не допускается.

Answer 1

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

Answer 2

Это можно сделать за O(n log n) время, если не требуется использовать дополнительное пространство.Стратегия будет состоять в том, чтобы сначала отсортировать массив за O(n log n), а затем разбить массив на четные и нечетные группы с помощью двух последовательных линейных сканирований, каждое из которых займет O(n).

Общая сложность составит O(n log n) + 2 * O(n) = O(n log n).

Если у нас будет больше информации о распределении чисел в массиве, можно было бы улучшить O(n log n) время, необходимое для сортировки массива, уменьшив общую сложность.

Код для этого можно увидеть на http://www.codeblocks.info/2010/10/sorting-array-with-all-even-numbers.html

Answer 3

class Program 
    {
        static void Main()
        {
          int[] numbers = { 1, 2, 3, 4, 5,6,7,8,9,10,11,12,13,14 };

         //using delegate
          Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);

          Array.ForEach(numbers, x => Console.Write(x));
          Console.WriteLine("");

         //using custom comparer
          CustomComparer comparer = new CustomComparer();
          Array.Sort(numbers, comparer);
          Array.ForEach(numbers, x => Console.Write(x));
          Console.WriteLine("");

          //using lambda
          int[] items = numbers.OrderBy(x => x % 2 == 0).ThenBy(x => x % 2).ToArray();

          Console.WriteLine("");
          Array.ForEach(items, x => Console.Write(x));
        }

        public int Compare(int x, int y)
        {
            return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
        }
    }

    public class CustomComparer : IComparer<int>
    {
        int IComparer<int>.Compare(int x, int y)
        {
            return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
        }
    }

Answer 4

Конечно, вы можете сделать это за O(n) время, используя O(n) дополнительной памяти.Вам нужна стабильная сортировка, и, по сути, вам необходимо выполнить первый шаг радикальной сортировки MSD (обычно знаковый бит является «наиболее значимым» битом, тогда как вас интересует четность / нечетность, но это та же самая базовая сделка),Радикальная сортировка может быть сделана стабильной с помощью отдельного буфера, содержащего либо значения 1, либо 0, а затем объедините их.

C ++ имеет алгоритм stable_partition, который делает именно то, что вы хотите.Он имеет O(n) сложность, если использует буфер, и O(n log n), если нет.Я не знаю технику для последнего.Я понимаю, что вопрос касается C, но вы можете скопировать и изменить код из любой стандартной реализации библиотеки C ++ или, возможно, использовать компилятор C ++, чтобы создать себе "extern C" функцию, которая вызывает stable_partition.