Ideas básicas
Radixsort se desarrolla en función de la clasificación de cubos, y ambas clasificaciones son implementaciones avanzadas de asignación de clasificación. La idea básica de DistributiveSt: el proceso de clasificación no requiere comparar palabras clave, sino que implementa la clasificación a través de los procesos de "distribución" y "recopilar". Su complejidad de tiempo puede alcanzar un orden lineal: O (n).
La clasificación de la cardinalidad es un algoritmo de clasificación estable, pero tiene ciertas limitaciones:
1. Las palabras clave pueden descomponerse.
2. El número de palabras clave registradas es menor, y es mejor si son densos. 3. Si es un número, es mejor estar sin firmar, de lo contrario, se aumentará la complejidad de mapeo correspondiente. Primero puedes ordenarlos por separado.
Echemos un vistazo a la clasificación de cubos (Radixsort).
La clasificación de cubos también se llama clasificación de caja (Binsort). Su idea básica es configurar varios cubos, escanear los registros que se ordenen R [0], R [1], ..., R [N-1], cargar todos los registros con palabras clave en un cierto rango en el cubo de KTH (asignado), y luego conecte las cabezas y colas de cada cubo no vacío en secuencia (recopilar) según el número de secuencia.
Por ejemplo, para ordenar 52 cartas de juego barajadas por puntos a <2 <... <j <k <k, se deben establecer 13 "cubos". Al clasificar, cada carta se coloca en el cubo correspondiente por puntos, y luego los cubos están conectados en secuencia para obtener un mazo de cartas dispuestas en orden incremental de puntos.
En la clasificación de cubos, el número de cubos depende del rango de valor de la palabra clave. Por lo tanto, la clasificación de cubos requiere que el tipo de palabra clave sea finito, de lo contrario, se pueden requerir cubos ilimitados.
En términos generales, es impredecible cuántos registros con las mismas palabras clave se almacenan en cada cubo, por lo que el tipo de cubo debe diseñarse como una lista vinculada.
Para garantizar que la clasificación sea estable, las conexiones durante el proceso de embalaje y recolección deben llevarse a cabo de acuerdo con el principio de primera salida.
Para la clasificación de cubos, el tiempo del proceso de asignación es o (n); El tiempo del proceso de recolección es O (M) (se utiliza una lista vinculada para almacenar la entrada para clasificar los registros) o O (M+N). Por lo tanto, el tiempo para la clasificación de cubos es O (M+N). Si el orden de magnitud del número de cubos m es o (n), el tiempo de clasificación de cubos es lineal, es decir, o (n).
La mayor parte de la complejidad del tiempo de los principales algoritmos de clasificación mencionados anteriormente es O (N2), y algunos algoritmos de clasificación son O (NLOGN). Pero la clasificación de barril puede lograr la complejidad del tiempo de O (N). Sin embargo, las desventajas de la clasificación de cubos son: en primer lugar, la complejidad del espacio es relativamente alta y se requiere la sobrecarga adicional. La clasificación tiene dos conjuntos de espacios en lo alto, uno almacena la matriz para ordenarse, y la otra es el llamado cubo. Por ejemplo, el valor que se ordenará es de 0 a M-1, luego se requieren cubos M, y esta matriz de deseos requiere al menos m espacio. En segundo lugar, los elementos a ordenar deben estar dentro de un rango determinado, etc.
La clasificación de la cardinalidad es una mejora en la clasificación de cubos, lo que hace que la "clasificación de cubos" sea adecuada para conjuntos de valores de elementos más grandes en lugar de mejorar el rendimiento.
Usemos el ejemplo de las cartas para ilustrar. Una tarjeta consta de dos palabras clave: traje (Peach <Heart <Mei <Square) + Valor facial (A <2 <3 <4 <... <k). Si el tamaño de una tarjeta está determinado primero por el traje, y las tarjetas de la misma demanda están determinadas por el número. Tenemos dos algoritmos para resolver este problema.
Es decir, si los trajes son diferentes, sin importar cuál sea el valor nominal, la tarjeta con un color de traje inferior es más pequeño que el color del traje con un color de traje más alto. Solo en el mismo color del traje, la relación de tamaño está determinada por el tamaño del valor nominal. Este es el orden de múltiples códigos clave.
Para obtener resultados de clasificación, discutimos dos métodos de clasificación.
Método 1: Primero ordene los trajes y colores y divídalos en 4 grupos, a saber, Grupo de flores de ciruela, grupo cuadrado, grupo de corazón rojo y grupo de corazón negro. Luego ordene cada grupo por valor nominal y, finalmente, conecte los 4 grupos juntos.
Método 2: Primero, dé 13 grupos de números (No. 2, 3, ..., a) de acuerdo con 13 valores faciales, coloque las tarjetas en los grupos de números correspondientes en orden de acuerdo con los valores faciales y divídalos en 13 pilas. Luego, dé 4 grupos de numeración (flores de ciruela, cuadrados, corazones rojos, corazones negros), saque las tarjetas en el Grupo 2 y póngalas en el grupo de color correspondiente, y luego saque las tarjetas en el Grupo 3 y colóquelas en el grupo de color correspondiente, ... de esta manera, todos los 4 grupos de color se ordenan de acuerdo con el valor facial, y luego, conectan los 4 grupos de color en la secuencia.
La clasificación del código de clave múltiple se ordena en orden desde el código de la clave principal al segundo código de la clave o desde la segunda clave al código de la tecla principal, y se divide en dos métodos:
El método de prioridad de bits más significativo (Most SignificanteDigitFirst), denominado método MSD:
1) Primero clasifique y agrupe por K1, divida la secuencia en varias subsecuencias. En los registros del mismo grupo de secuencias, los códigos clave K1 son iguales.
2) Luego ordene cada grupo en subgrupos por K2. Después de eso, continúe clasificando los siguientes códigos clave de esta manera hasta que cada subgrupo esté ordenado por el código clave más secundario KD.
3) Luego conecte los grupos para obtener una secuencia ordenada. El método introducido en las tarjetas de clasificación por trajes y valores faciales es el método MSD.
El método de DigitFirst menos significativo, denominado método LSD:
1) Comience a clasificar desde KD, luego ordene KD-1, repitiendo a su vez hasta que se divide en la posterior posterior más pequeña según K1.
2) Finalmente, conecte cada subsecuencia para obtener una secuencia ordenada. El segundo método introducido en las tarjetas de clasificación por traje y valor nominal es el método LSD.
Una sola palabra clave de un tipo numérico o de caracteres puede considerarse como una palabra múltiple compuesta de múltiples dígitos o múltiples caracteres. En este momento, el método de "asignación de recolección" se puede usar para ordenarlo. Este proceso se llama método de clasificación de cardinalidad, donde el número de valores posibles para cada número o carácter se llama cardinalidad. Por ejemplo, la base de trajes de cartas de juego es 4 y la base del valor nominal es 13. Al clasificar a las cartas, puede organizarlos primero por el estilo o por el valor nominal primero. Al clasificar de acuerdo con los colores, primero divídalo en 4 pilas (distribuciones) en el orden de rojo, negro, cuadrado y flores, luego apilarlos (recolectar) en este orden, y luego divídelas en 13 pilas (distribuciones) en el orden de valor nominal, y luego apilarlas (recolectar) en este orden. De esta manera, la asignación y colección secundaria pueden organizar las cartas de juego de manera ordenada.
Durante el proceso de "asignación de recolección", se debe garantizar la estabilidad de la clasificación.
La idea de la clasificación de la cardinalidad es cubrir cada grupo de palabras clave en los datos que se ordenarán en secuencia. Por ejemplo, la siguiente secuencia se ordenará:
135, 242, 192, 93, 345, 11, 24, 19
Dividimos los dígitos individuales, diez y cientos de cada valor en tres palabras clave, por ejemplo:
135-> K1 (dígitos únicos) = 5, K2 (diez dígitos) = 3, k3 (cien dígitos) = 1.
Luego, comience desde el bit más bajo (a partir de la última palabra clave), todas las palabras clave K1 de todos los datos están alocadas con cubo (porque cada número es 0-9, por lo que el tamaño del cubo es 10), y luego emiten los datos en el cubo en secuencia para obtener la siguiente secuencia.
(11), (242, 192), (93), (24), (135, 345), (19) (clasificación a partir de la palabra más clave, ignorando los ciento diez dígitos y asignando de acuerdo con los números en los dígitos únicos)
Entonces la secuencia anterior se asigna para K2, y la secuencia de salida es:
(11, 19), (24), (135), (242, 345), (192, 93) (consulte la palabra más clave para ordenar la segunda palabra clave, ignorar los cientos de dígitos individuales y asignar de acuerdo con el número en los diez dígitos)
Finalmente, para la asignación de deseos de K3, la secuencia de salida es:
(011, 019, 024, 093), (135, 192), (242), (345) (consulte la segunda palabra clave para ordenar la palabra clave más alta, ignorar los diez y un solo dígitos, y asignarlos de acuerdo con los números en los cien dígitos)
La clasificación está completa.
Implementación de Java
public void radixsort () {int max = array [0]; for (int i = 0; i <array.length; i ++) {// Encuentre el valor máximo en la matriz if (array [i]> max) {max = array [i]; }} int keySnum = 0; // El número de palabras clave, usamos dígitos únicos, diez dígitos y cientos ... como palabras clave, por lo que el número de palabras clave es el dígito máximo mientras (max> 0) {max /= 10; Keysnum ++; } List <ArrayList <Integer>> buckets = new ArrayList <ArrayList <Integer>> (); para (int i = 0; i <10; i ++) {// El número posible para cada dígito es 0 ~ 9, así que configure 10 cubos. // El cubo está compuesto de ArrayList <integer>} para (int i = 0; i <keysnum; i ++) {// Comience con la palabra clave más reciente, asigna de acuerdo con las palabras clave a su vez para (int j = 0; j <array.length; j ++) {// escane todos los elementos y asigna elementos a los elementos para el cubo correspondiente. Elemento, como 258. Ahora necesita sacar el número en los diez dígitos, 258%100 = 58,58/10 = 5 int Key = Array [J]%(int) Math.Pow (10, i+1)/(int) Math.Pow (10, I); buckets.get (clave) .Add (Array [j]); // Coloque este elemento en un cubo con la tecla de palabra clave} // Después de asignar, copie los elementos en el cubo de nuevo a la matriz int contador = 0; // contador de elementos para (int j = 0; j <10; j ++) {ArrayList <integer> bucket = buckets.get (j); // cubo con palabra clave j while (bucket.size ()> 0) {array [contador ++] = bucket.remove (0); // Copiar el primer elemento en el cubo a la matriz y eliminar}} system.out.print ("hilo"+(i+1)+"sort de ruedas:"); mostrar(); }}Los resultados de la impresión son los siguientes:
Análisis de algoritmo
A primera vista, la eficiencia de ejecución del orden de cardinalidad parece ser buena y es increíble que todo lo que tiene que hacer es copiar los elementos de datos originales de la matriz a la lista vinculada y luego copiarlos de nuevo. Si hay 10 elementos de datos, hay 20 réplicas, repitiendo el proceso para cada bit. Suponiendo que se ordenen los números de 5 dígitos, se requieren 20*5 = 100 copias. Si hay 100 elementos de datos, entonces hay 200*5 = 1000 copias. El número de copias es proporcional al número de elementos de datos, es decir, o (n). Este es el algoritmo de clasificación más eficiente que hemos visto.
Desafortunadamente, cuantos más elementos de datos, más largas se necesitan palabras clave. Si los elementos de datos se incrementan en 10 veces, la palabra clave debe agregarse en una (una ronda más de clasificación). El número de copias y el número de elementos de datos son proporcionales a la longitud de la palabra clave, y se puede considerar que la longitud de la palabra clave es el logaritmo de N. Por lo tanto, en la mayoría de los casos, la eficiencia de ejecución de la clasificación cardinal se invierte a O (N*logn), que es casi la misma que la clasificación rápida.
Resumir
Lo anterior es todo el contenido de este artículo sobre la introducción a la clasificación de la cardinalidad y la implementación del lenguaje Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo.