Io farei così:

codice:
import java.util.*;

public class Prova
{
    public static void main (String[] args)
    {
        int[] dati = { 34, 12, 17, 22, 8, 5, 9, 11, 45 };

        System.out.println ("PRIMA: " + Arrays.toString(dati));

        for (int i = 0; i < dati.length; i++)
        {
            for (int j = i; j < dati.length; j++)
            {
                if (dati[j] % 2 == i % 2)
                {
                    int t = dati[j];
                    
                    for (int k = j; k > i; k--)
                        dati[k] = dati[k-1];

                    dati[i] = t;
                    break;
                }
            }
        }

        System.out.println ("DOPO: " + Arrays.toString(dati));
    }
}
L'algoritmo che ho pensato credo sia interessante.