Nous introduisons ici un algorithme efficace qui peut être complété dans une complexité temporelle O(n).
L'idée principale est la suivante : définir deux pointeurs, un pointeur A balayant d'avant en arrière et un pointeur B balayant d'arrière en avant. Le pointeur A scanne un nombre pair et fait une pause, le pointeur B scanne un nombre impair et fait une pause, puis échange les deux nombres. Après l'échange, continuez à numériser et à échanger comme ci-dessus jusqu'à ce que le pointeur A et le pointeur B coïncident et s'arrêtent.
Le code Java de cet algorithme est le suivant :
Copiez le code comme suit :
Réorganisation du colis ;
classe publique Réorganiser {
public static void main (String[] arguments) {
int[] liste = { 1, 2, 3, 4, 5, 7, 9, 11 };
réorganiserOddEven(liste);
}
public static void reorderOddEven (liste int[]) {
int longueur = liste.longueur;
pour (int i = 0; i < longueur; i++) {
System.out.print(liste[i] + " );
}
System.out.print("/n");
int début = 0 ;
int fin = longueur - 1 ;
tandis que (début < fin) {
while (begin < end && (list[begin] & 0x1) != 0)
commencer++;
while (début < fin && (liste[fin] & 0x1) == 0)
fin--;
si (début < fin) {
int temp = liste[début];
liste[début] = liste[fin];
liste[fin] = temp;
}
}
pour (int i = 0; i < longueur; i++) {
System.out.print(liste[i] + " );
}
}
}