Aquí presentamos un algoritmo eficiente que se puede completar con una complejidad de tiempo O (n).
La idea central es: definir dos punteros, un puntero A escanea de adelante hacia atrás y un puntero B escanea de atrás hacia adelante. El puntero A escanea hasta un número par y hace una pausa, el puntero B escanea hasta un número impar y hace una pausa, y luego intercambia los dos números. Después del intercambio, continúe escaneando e intercambiando como se indicó anteriormente hasta que el puntero A y el puntero B coincidan y se detengan.
El código Java de este algoritmo es el siguiente:
Copie el código de código de la siguiente manera:
Reordenar paquete;
clase pública Reordenar {
público estático vacío principal (String [] argumentos) {
int[] lista = { 1, 2, 3, 4, 5, 7, 9, 11 };
reordenarOddEven(lista);
}
reorderOddEven vacío estático público (int [] lista) {
int longitud = lista.longitud;
para (int i = 0; i < longitud; i++) {
System.out.print(lista[i] + " ");
}
System.out.print("/n");
int comienzo = 0;
int final = longitud - 1;
mientras (comienzo <fin) {
mientras (comienzo <fin && (lista[comienzo] & 0x1) != 0)
comenzar++;
mientras (comienzo <fin && (lista[fin] & 0x1) == 0)
fin--;
si (comienzo <fin) {
int temp = lista[comienzo];
lista[comienzo] = lista[fin];
lista[fin] = temporal;
}
}
para (int i = 0; i < longitud; i++) {
System.out.print(lista[i] + " ");
}
}
}