Programa de Python para reorganizar números positivos y negativos en tiempo O (n) y espacio adicional O (1)

Una array contiene números positivos y negativos en orden aleatorio. Reorganice los elementos de la array para que los números positivos y negativos se coloquen alternativamente. El número de números positivos y negativos no tiene por qué ser igual. Si hay más números positivos, aparecen al final de la array. Si hay más números negativos, también aparecen al final de la array.
Por ejemplo, si la array de entrada es [-1, 2, -3, 4, 5, 6, -7, 8, 9], la salida debería ser [9, -7, 8, -3, 5, – 1, 2, 4, 6]
Nota: El proceso de partición cambia el orden relativo de los elementos. Es decir, con este enfoque no se mantiene el orden de aparición de los elementos. Vea esto para mantener el orden de aparición de los elementos en este problema.
La solución es separar primero los números positivos y negativos usando el proceso de partición de QuickSort. En el proceso de partición, considere 0 como valor del elemento pivote para que todos los números negativos se coloquen antes de los números positivos. Una vez que se separan los números negativos y positivos, comenzamos con el primer número negativo y el primer número positivo e intercambiamos cada número negativo alternativo con el siguiente número positivo. 
 

#  Python program to put positive numbers at even indexes (0,  // 2, 4,..) and
#  negative numbers at odd indexes (1, 3, 5, ..)
 
# The main function that rearranges elements of given array.
# It puts  positive elements at even indexes (0, 2, ..) and
# negative numbers at odd indexes (1, 3, ..).
def rearrange(arr, n):
    # The following few lines are similar to partition process
    # of QuickSort.  The idea is to consider 0 as pivot and
    # divide the array around it.
    i = -1
    for j in range(n):
        if (arr[j] < 0):
            i += 1
            # swapping of arr
            arr[i], arr[j] = arr[j], arr[i]
  
    # Now all positive numbers are at end and negative numbers
    # at the beginning of array. Initialize indexes for starting
    # point of positive and negative numbers to be swapped
    pos, neg = i+1, 0
  
    # Increment the negative index by 2 and positive index by 1,
    # i.e., swap every alternate negative number with next
    # positive number
    while (pos < n and neg < pos and arr[neg] < 0):
 
        # swapping of arr
        arr[neg], arr[pos] = arr[pos], arr[neg]
        pos += 1
        neg += 2
 
# A utility function to print an array
def printArray(arr, n):
     
    for i in range(n):
        print arr[i],
  
# Driver program to test above functions
arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9]
n = len(arr)
rearrange(arr, n)
printArray(arr, n)
 
# Contributed by Afzal

Producción:  

    4   -3    5   -1    6   -7    2    8    9

Complejidad de tiempo: O (n) donde n es el número de elementos en una array dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo 
Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional.
 

Consulte el artículo completo sobre Reorganizar números positivos y negativos en tiempo O(n) y espacio adicional O(1) para obtener más detalles.