Как отсортировать некоторые элементы и оставить других в Java?

Ответ 1

Простое решение для грубой силы:

• итерация входного массива и извлечение всех нечетных чисел
• собирать нечетные числа в новом меньшем массиве
• сортировать этот массив
• теперь снова перемещаем исходный массив: всякий раз, когда вы находите нечетное число, вы выбираете "следующую" запись из нечетного массива

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

Пример реализации (спасибо Daniel Foerster):

public static int[] sortFiltered(int[] src, IntPredicate predicate) {
  int[] filtered = IntStream.of(src).filter(predicate).sorted().toArray();
  int[] dst = new int[src.length];
  for (int i = 0, j = 0; i < src.length; i++) {
    dst[i] = predicate.test(src[i]) ? filtered[j++] : src[i];
  }
  return dst;
}

Вызов с фильтром для нечетных чисел:

sortFiltered(array, (n) -> n % 2 != 0);

Как вы можете видеть, этот алгоритм не зависит от конкретного типа предиката или массива/списка. Но поскольку он использует IntStream и Лямбда-выражения, для этого требуется Java 8 или новее.

Ответ 2

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

public class MyClass {
    public static void main(String args[]) {
        int temp;
        //odd numbers are sorted, even number stay where they are
        //Expected output: 1, 3, 2, 8, 5, 4
        int array[] = {5, 3, 2, 8, 1, 4};
        int[] sortedArray = new int[array.length];
        for (int j = 0; j < array.length - 1; j++) {
            for (int x = 0; x < array.length - 1; x++) {

                while(array[x] % 2 == 0 && x < array.length-1){
                    x++;
                }

                int y = x+1;

                if(y < array.length) {
                    while (array[y] % 2 == 0 && y < array.length - 1) {
                        y++;
                    }

                    if (array[x] > array[y] && array[y] % 2 == 1 && array[x] % 2 == 1) {
                        temp = array[x];
                        array[x] = array[y];
                        array[y] = temp;
                        sortedArray = array;
                    }
                }
            }
        }
        for (int i: sortedArray) {
            System.out.println(i);
        }
    }
}

Это приводит к:

1 3 2 8 5 4

Ответ 3

Ваш код похож на вид пузыря, но с этим вы только сравниваете каждого прямого соседа. Вот рабочий код, который использует 2 для циклов и работает на месте. Он не обязательно сравнивает прямых соседей, но вместо этого он ищет очередное нечетное число для сравнения с текущим нечетным числом.

Далее произошла небольшая ошибка при копировании вашего array в sortedArray, потому что вы делаете это: sortedArray = array; в своем цикле, который просто копирует ссылку на массив. В рабочем коде ниже я взял ваше решение и изменил его. Я также просто скопирую массив до начала сортировки, чтобы исходный массив не изменился.

Внутренний цикл цикла начинается с индекса внешнего для цикла плюс 1. Кроме того, внутренний цикл просто петли до одного элемента до конца. В худшем случае потребуются операции n-1 * n/2 = n^2/2 - n/2, которые приводят к O(n^2), как обычная сортировка пузырьков.

Код и рабочий пример на ideone:

public class MyClass
{
   public static void main(String args[])
   {
      int array[] = {5, 3, 2, 8, 1, 4};

      int[] sortedArray = new int[array.length];
      System.arraycopy(array, 0, sortedArray, 0, array.length);

      for (int i = 0; i < sortedArray.length - 1; i++)
      {
         /* is current odd, if so search next odd */
         if (sortedArray[i] % 2 != 0)
         {
            /* search for next odd and compare */
            for (int j = i + 1; j < sortedArray.length; j++)
            {
               if ((sortedArray[j] % 2 != 0) && (sortedArray[i] > sortedArray[j]))
               {
                  int temp = sortedArray[i];
                  sortedArray[i] = sortedArray[j];
                  sortedArray[j] = temp;
               }
            }
         }
      }
      for (int i: sortedArray)
      {
         System.out.println(i);
      }
   }
}

Вывод:

1
3
2
8
5
4

Ответ 4

Данный несортированный массив A: Создайте 2 экземпляра Vector O и E, содержащие нечетные и четные элементы массива, по порядку. (все примеры кода являются псевдокодами. "до" в цикле означает, что правая сторона префикса не включена, в соответствии с нумерацией со стандартным массивом)

for i in 0 up to A.length: if A[i] is odd, append it to O, else append it to E

Создайте отдельный массив логических элементов B следующим образом:

for i in 0 up to A.length: if A[i] is odd, B[i] = true, else B[i] = false

Сортировка O в новый вектор S (в порядке возрастания). Я рекомендую использовать встроенный сорт Java, поскольку он будет намного эффективнее, чем сортировка пузыря, и другие ответы утверждают, что вы используете.

S = ascendingSort(O)

Определите операцию pop, которая возвращает первый элемент в векторе, а затем удаляет его из вектора.

Создайте новый пустой вектор R, а затем реализуйте следующий псевдокод:

for i in 0 up to B.length: if B[i] is true, then append pop(S) to R, else append pop(E) to R.

В результате результат R.

Почему это работает:

Сначала отделите шансы от эвенов, чтобы скрыть эвенки от сортировки, сохранив их первоначальный порядок (векторы O и E). Поддерживайте позиции (вектор B) нечетных/четных элементов в исходном массиве.

Сортировать коэффициенты (вектор S).

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