Ordenación por Residuos - Radix Sort

El método de ordenación por residuos, o RadixSort, utiliza una aproximación diferente a la de comparar los elementos del arreglo entre sí. En vez de esto, este algoritmo recorre el arreglo trasladando cada elemento a una cola determinada por el residuo, o dígito menos significativo del número. Cuando todos los elementos han sido trasladados a las colas, se recorren todas las colas en orden trasladando ahora los elementos al vector. El proceso se repite ahora para los demás dígitos de los elementos del vector.

Si bien se habla de digitos (unidades, decenas, centenas, etc), para un computador es más eficiente hacer las operaciones a nivel de bit, con desplazamientos, que las operaciones de división y residuo. Por tal motivo, la implementación que se presenta a continuación utiliza corrimientos de 4 bits, que se pueden representar como dígitos hexadecimales.

public static void ordenacionResiduos(int[] v) {
        int max    = 1;     // cantidad de repeticiones
        int nbytes = 4;     // numero de bytes a desplazar
        int nColas = (int) Math.pow(2,nbytes) ;
        // Creación e inicialización del arreglo de colas
        Queue<Integer>[] cola = new LinkedList[nColas];
        for(int i=0; i<nColas; i++) cola[i]=new LinkedList<Integer>();

        int     div     = 0;        // posición a comparar
        for(int i=0; i<max; i++) {
            // parte 1: recorrer el vector  para guardar cada elemento
            // en la cola correspondiente
            for(int numero: v) {
                // buscar el mayor número del vector
                if(i==0) if(numero>max) max=numero;
                // calcular en qué cola debe ir cada número
                int numCola = (numero>>div) & 0xf;
                cola[numCola].add(numero);
            }
            div = div+nbytes;

            // parte 2: recorrer las colas en orden para poner cada
            // elemento en el vector;
            int j=0;
            for(Queue<Integer> c: cola) {
                while(!c.isEmpty()) v[j++]=c.remove();
            }
            // la primera vez se actualiza el número de veces que se
            // debe ejecutar el proceso
            if(i==0) { max = (int) (Math.log(max)/Math.log(nColas)) + 1; }
        }
    }

La complejidad de este algoritmo es lineal, O(NxM), donde N es el número de elementos del arreglo y M es el número de dígitos del mayor elemento del vector.