Classifique números em uma matriz sem alterar a posição dos números pares usando Java-8

Estou aprendendo fluxos Java 8. Diga-me, como posso escrever um sortArraymétodo de forma mais compacta?

import org.junit.Test;    
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import static org.junit.Assert.assertArrayEquals;

public class TestStream {

    /*
     * Sort numbers in an array without changing even numbers position
     */

    @Test
    public void test_1() {
        int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};
        int[] expected = new int[]{1, 4, 3, 2, 5, 6, 7, 8, 9, 0};

        Integer[] arr = sortArray(nonSorted);
        int[] sorted = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sorted[i] = arr[i];
        }

        assertArrayEquals(expected, sorted);
    }

    private Integer[] sortArray(int[] array) {
        Map<Integer, Integer> even = extractEven(array);
        Integer[] withoutEvens = removeEven(array);
        int length = even.size() + withoutEvens.length;
        Integer[] result = new Integer[length];
        Arrays.sort(withoutEvens);
        for (int i = 0; i < withoutEvens.length; i++) {
            result[i] = withoutEvens[i];
        }
        even.forEach((k, v) -> {
            System.arraycopy(result, k, result, k + 1, length - k - 1);
            result[k] = v;
        });

        return result;
    }


    private Map<Integer, Integer> extractEven(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                map.put(i, array[i]);
            }
        }

        return map;
    }

    private Integer[] removeEven(int[] array) {
        ArrayList<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                list.add(array[i]);
            }
        }

        Integer[] a = new Integer[list.size()];
        return list.toArray(a);
    }
}

Pode-se pensar em uma solução como: Primeiro extraímos os inteiros ímpares do nonSorted[]e os colocamos de maneira stackordenada.

Por que devemos usar o de stackforma ordenada?

A matriz final precisa ser classificada de maneira ímpar Integers, a pilha segue a política FIFO (primeiro a sair).

Agora vamos levar um Instreame executá-lo a partir 0para nonSorted.length-1e verificar o original nonSortedpara o estranho Integer; assim que encontramos um, substituí-lo pelo primeiro elemento da pilha e pop()o elemento do stack.

Nota: É necessário jogar ao redor da pilha, pois nem sempre você precisará de elementos classificados na pilha, mas, no caso do OP, isso acontece.

int[] nonSorted = new int[]{3, 4, 5, 2, 1, 6, 9, 8, 7, 0};

LinkedList<Integer> stack = Arrays.stream(nonSorted)
            .sorted().filter(s -> s % 2 != 0).boxed()
            .collect(Collectors.toCollection(LinkedList::new));

int[] expected = IntStream.rangeClosed(0, nonSorted.length - 1)
       .map(s -> nonSorted[s] % 2 != 0 ? stack.pop():nonSorted[s]) 
       .toArray();

Eu realmente gostei da idéia de usar um ordenado Stack, mas não é facilmente paralelizável e fiquei curioso em como resolver isso.

Minha idéia é classificar índices de elementos desiguais e, dependendo da posição do índice, podemos distinguir durante a criação da matriz de resultados se um número é par ou não.

public int[] sortUnevenElements(int[] nonSorted) {
    int[] unevenIndices = IntStream.range(0, nonSorted.length).filter(i -> nonSorted[i] % 2 != 0).toArray();
    int[] sortedUnevenIndices = Arrays.stream(unevenIndices, 0, unevenIndices.length).boxed()
          .sorted(Comparator.comparingInt(i -> nonSorted[i])).mapToInt(Integer::intValue).toArray();
    return IntStream.range(0, nonSorted.length).map(i -> {
        int idx = Arrays.binarySearch(unevenIndices, i);
        return idx >= 0 ? nonSorted[sortedUnevenIndices[idx]] : nonSorted[i];
    }).toArray();
}

Acredito que o que você quer dizer com Java-8 é usar se Streamoutras APIs introduzidas desde esse lançamento. Você já tem um código com muito bom desempenho na minha opinião. A maneira que eu poderia pensar em resolver o problema é a seguinte -

1. Encontre os números ímpares e pares e seus mapeamentos para os índices atuais. De tal forma que valores iguais com seus índices permaneceriam fixos.

2. Sobre os números ímpares e seus índices, remapeie os valores ordenando-os naturalmente.

3. Feito tudo isso, mescle esses mapas pares e ímpares com base nos índices.

4. Recupere os valores desse resultado mesclado.

A implementação geral disso seria algo como -

private Integer[] sortArrayStream(Integer[] array) {
    Map<Boolean, Map<Integer, Integer>> evenOdds = IntStream.range(0, array.length)
            .boxed()
            .collect(Collectors.partitioningBy(i -> array[i] % 2 == 0,
                    Collectors.toMap(o -> o, i -> array[i]))); //1

    Map<Integer, Integer> oddSorted = remapWithSorting(evenOdds.get(Boolean.FALSE)); // 2

    Map<Integer, Integer> overall = new HashMap<>(evenOdds.get(Boolean.TRUE));
    overall.putAll(oddSorted); // part of 3

    return overall.entrySet().stream()
            .sorted(Map.Entry.comparingByKey()) // remaining of 3
            .map(Map.Entry::getValue) // 4
            .toArray(Integer[]::new); 
}


private Map<Integer, Integer> remapWithSorting(Map<Integer, Integer> initialIndexMapping) {
    List<Integer> oddIndexes = new ArrayList<>(initialIndexMapping.keySet());
    List<Integer> sortedOdds = initialIndexMapping.values().stream()
            .sorted().collect(Collectors.toList());
    return IntStream.range(0, sortedOdds.size())
            .boxed()
            .collect(Collectors.toMap(oddIndexes::get, sortedOdds::get));
}

Este é um teste de classificação por inserção com fluxos. A nonSortedmatriz é transmitida e coletada para a new int[]. Se o valor da nonSortedmatriz é par, apenas é copiado; caso contrário, se for ímpar, uma ordenação por inserção será executada apenas para valores ímpares já presentes no resultado.

int[] sort = IntStream.range(0, nonSorted.length)
            .collect(() -> new int[nonSorted.length], (ints, i) -> {
                ints[i] = nonSorted[i];
                if (nonSorted[i] % 2 != 0) {
                    AtomicInteger current = new AtomicInteger(i);
                    IntStream.iterate(i - 1, 
                                     (v) -> current.get() > 0 && v >= 0,
                                     (v) -> --v)
                            .forEach(ind -> {
                                if (ints[ind] % 2 != 0) {
                                    if (ints[ind] > nonSorted[i]) {
                                        ints[current.get()] = ints[ind];
                                        ints[ind] = nonSorted[i];
                                        current.set(ind);
                                    } else {
                                        current.set(-1);
                                    }
                                }
                            });
                }
            }, (a1, a2) -> {
            });