Можно ли сделать этот алгоритм лучше?

Question

У меня есть вопрос, в одном из алгоритмов, которые я написал, чтобы отделить все четные числа слева и нечетные числа справа.

Пример: Ввод:

{12, 10, 52, 57, 14, 91, 34, 100, 245, 78, 91, 32, 354, 80, 13, 67, 65}

Вывод:

{12,10,52,80,14,354,34,100,32,78,91,245,91,57,13,67 , 65}

Ниже приведен алгоритм

public int[] sortEvenAndOdd(int[] combinedArray) {
  int endPointer = combinedArray.length - 1;
  int startPointer = 0;
  for (int i = endPointer; i >= startPointer; i--) {
    if (combinedArray[i] % 2 == 0) {
      if (combinedArray[startPointer] % 2 != 0) {
        int temp = combinedArray[i];
        combinedArray[i] = combinedArray[startPointer];
        combinedArray[startPointer] = temp;
        startPointer = startPointer + 1;
      } else {
        while (combinedArray[startPointer] % 2 == 0 &&
          (startPointer != i)) {
          startPointer = startPointer + 1;
        }
        int temp = combinedArray[i];
        combinedArray[i] = combinedArray[startPointer];
        combinedArray[startPointer] = temp;
        startPointer = startPointer + 1;
      }
    }
  }
  return combinedArray;
}

Кто-нибудь, есть какие-либо предложения, для того, чтобы сделать это O (n) или лучше?

Answer 1

Ваш код O (n), но он немного сложнее, чем нужно. Вот улучшение.

startPointer = 0;
endPointer = a.length - 1;
while (startPointer < endPointer)
{
    if (a[startPointer] % 2 != 0)
    {
        // move endPointer backwards to even number
        while (endPointer > startPointer && a[endPointer] % 2 != 0)
        {
            --endPointer;
        }
        swap(a[startPointer], a[endPointer]);
    }
    ++startPointer;
}

Кстати, операция - это больше раздел, чем сортировка. Я думаю, что лучшее имя функции будет partitionEvenOdd.

Answer 2

Вы не можете сделать это лучше, чем O (n) раз, но вы можете сделать свой код более кратким.

Глядя на свое решение, поскольку порядок элементов не имеет значения, вы можете просто сохранить переменная-указатель, которая идет от последнего к первому и содержит элементы обмена с этим указателем.

Фрагмент:

private static void solve(int[] arr){
    for(int i=arr.length-1,ptr = i;i>=0;--i){
        if((arr[i] & 1) == 1){
            swap(arr,i,ptr--);
        }
    }
}   

private static void swap(int[] arr,int x,int y){
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

Демонстрация: https://onlinegdb.com/HyKNVMbwL

---

Если порядок элементов имеет значение

• Вы можете собрать все нечетные в новом списке.
• Переместить все четные влево.
• Назначить все нечетные один за другим из списка в массив, где заканчивались четные единицы.
• Это увеличит сложность пространства до O (n).

Answer 3

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

Извините за engli sh.

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