Dada una serie de dígitos, ¿cómo los clasifica con la complejidad temporal o (n)?

Puede encontrar la complejidad de tiempo O (n) para ordenar una matriz de dígitos en el mejor caso de ordenación por inserción ( eficiente para conjuntos de datos que ya están sustancialmente ordenados: la complejidad de tiempo es O (nk) cuando cada elemento en la entrada no es más que k se aleja de su posición ordenada ).

Pero, en general, tenemos a lo sumo la complejidad del tiempo O (nlogn) para la clasificación de algoritmos como la combinación de clasificación, clasificación de montón, clasificación rápida (el mejor de los casos).

Ok, si insistes más, entonces puedo llevarte a Conteo de clasificación – GeeksforGeeks, pero necesita espacio adicional. La clasificación de conteo es una técnica de clasificación basada en teclas entre un rango específico. Funciona contando el número de objetos que tienen valores clave distintos (tipo de hash). Luego haciendo algo de aritmética para calcular la posición de cada objeto en la secuencia de salida.

Vamos a entenderlo con la ayuda de un ejemplo.

  Para simplificar, considere los datos en el rango de 0 a 9. 
 Datos de entrada: 1, 4, 1, 2, 7, 5, 2
   1) Tome una matriz de conteo para almacenar el conteo de cada objeto único.
   Índice: 0 1 2 3 4 5 6 7 8 9
   Recuento: 0 2 2 0 1 1 0 1 0 0

   2) Modifique la matriz de conteo de modo que cada elemento en cada índice 
   almacena la suma de los recuentos anteriores. 
   Índice: 0 1 2 3 4 5 6 7 8 9
   Cuenta: 0 2 4 4 5 6 6 7 7 7

 La matriz de recuento modificada indica la posición de cada objeto en 
 La secuencia de salida.
 
   3) Salida de cada objeto de la secuencia de entrada seguido de 
   disminuyendo su recuento en 1.
   Procese los datos de entrada: 1, 4, 1, 2, 7, 5, 2. La posición de 1 es 2.
   Ponga los datos 1 en el índice 2 en la salida.  Disminuya el recuento en 1 para colocar 
   siguiente dato 1 en un índice 1 más pequeño que este índice.

Complejidad de tiempo: O (n + k) donde n es el número de elementos en la matriz de entrada yk es el rango de entrada.
Espacio auxiliar: O (n + k)

Salud !!!!

Contar Ordenar – GeeksforGeeks