Programa Java para reorganizar una array tal que arr[i] >= arr[j] si i es par y arr[i]<=arr[j] si i es impar y j <i

Dada una array de n elementos. Nuestra tarea es escribir un programa para reorganizar el arreglo de modo que los elementos en las posiciones pares sean mayores que todos los elementos anteriores y los elementos en las posiciones impares sean menores que todos los elementos anteriores.
Ejemplos: 
 

Input : arr[] = {1, 2, 3, 4, 5, 6, 7}
Output : 4 5 3 6 2 7 1

Input : arr[] = {1, 2, 1, 4, 5, 6, 8, 8} 
Output : 4 5 2 6 1 8 1 8

La idea para resolver este problema es crear primero una copia auxiliar de la array original y ordenar la array copiada. Ahora el número total de posiciones pares en la array con n elementos será piso (n/2) y el resto es el número de posiciones impares. Ahora llene las posiciones pares e impares en la array original usando la array ordenada de la siguiente manera: 
 

• El total de posiciones impares será n – piso (n/2). Comience desde (n-piso (n/2)) la posición en la array ordenada y copie el elemento en la primera posición de la array ordenada. Comience a recorrer la array ordenada desde esta posición hacia la izquierda y siga llenando las posiciones impares en la array original hacia la derecha.
• Comience a recorrer la array ordenada a partir de (n-piso (n/2) + 1) ª posición hacia la derecha y siga llenando la array original a partir de la segunda posición. 
   

A continuación se muestra la implementación de la idea anterior: 
 

// Java program to rearrange the array
// as per the given condition
import java.util.*;
import java.lang.*;
 
public class GfG{
    // function to rearrange the array
    public static void rearrangeArr(int arr[],
                                        int n)
    {
        // total even positions
        int evenPos = n / 2;
 
        // total odd positions
        int oddPos = n - evenPos;
 
        int[] tempArr = new int [n];
 
        // copy original array in an
        // auxiliary array
        for (int i = 0; i < n; i++)
            tempArr[i] = arr[i];
 
        // sort the auxiliary array
        Arrays.sort(tempArr);
 
        int j = oddPos - 1;
 
        // fill up odd position in
        // original array
        for (int i = 0; i < n; i += 2) {
            arr[i] = tempArr[j];
            j--;
        }
 
        j = oddPos;
 
        // fill up even positions in
        // original array
        for (int i = 1; i < n; i += 2) {
            arr[i] = tempArr[j];
            j++;
        }
 
        // display array
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
     
    // Driver function
    public static void main(String argc[]){
        int[] arr = new int []{ 1, 2, 3, 4, 5,
                                        6, 7 };
        int size = 7;
        rearrangeArr(arr, size);
         
    }
}
 
/* This code is contributed by Sagar Shukla */

Producción: 
 

4 5 3 6 2 7 1

Complejidad de tiempo: O(N*logN), ya que estamos usando una función de clasificación.

Espacio Auxiliar: O(N), ya que estamos usando espacio extra.
 

Consulte el artículo completo sobre Reorganizar array de manera que arr[i] >= arr[j] si i es par y arr[i]<=arr[j] si i es impar yj <i para obtener más detalles.