Aqui apresentamos um algoritmo eficiente que pode ser concluído dentro de uma complexidade de tempo O(n).
A ideia central é: definir dois ponteiros, um ponteiro A varre de frente para trás e um ponteiro B varre de trás para frente. O ponteiro A faz a varredura para um número par e faz uma pausa, o ponteiro B faz a varredura para um número ímpar e faz uma pausa e, em seguida, troca os dois números. Após a troca, continue a varredura e a troca como acima até que o ponteiro A e o ponteiro B coincidam e parem.
O código Java deste algoritmo é o seguinte:
Copie o código do código da seguinte forma:
reordenar pacote;
classe pública Reordenar {
public static void main(String[] args) {
int[] lista = { 1, 2, 3, 4, 5, 7, 9, 11 };
reordenarOddEven(lista);
}
public static void reorderOddEven(int[] lista) {
comprimento interno = lista.comprimento;
for (int i = 0; i < comprimento; i++) {
System.out.print(lista[i] + " ");
}
System.out.print("/n");
int início = 0;
int fim = comprimento - 1;
while (início <fim) {
while (início <fim && (lista[início] & 0x1) != 0)
começar++;
while (início <fim && (lista[fim] & 0x1) == 0)
fim--;
if (início <fim) {
int temp = lista[início];
lista[início] = lista[fim];
lista[fim] = temp;
}
}
for (int i = 0; i < comprimento; i++) {
System.out.print(lista[i] + " ");
}
}
}