Prefacio: El tema de las estructuras y algoritmos de datos Java se actualizará de vez en cuando. Los lectores son bienvenidos a supervisarlo. Este artículo comienza con el algoritmo de clasificación más simple: clasificación de deseos y analiza las ideas de implementación, la implementación del código, las características de rendimiento y los escenarios aplicables de la clasificación de cubos.
0. Otros índices de algoritmo de clasificación
//www.vevb.com/article/120879.htm
1. idea de clasificación de cubos
Un ejemplo simple:
Clasificando los puntajes de las pruebas de inglés de 6 personas (1 ~ 10 puntos). Si el puntaje es [6, 5, 8, 8, 10, 9], la idea de clasificar con cubos es preparar 10 cubos, los números son 1 ~ 10 en secuencia, y los puntajes se colocan en los cubos correspondientes, como 6 puntos en el cubo No. 6, y dos 8 puntos en el cubo No. 8 ... y luego los emiten uno por uno de acuerdo con el orden de los números de cubos (si no hay, si no hay, si no hay, no hay, no hay, no hay, no hay, no existe, no hay una salida). Esta es la idea básica de la clasificación de cubos.
De hecho, esta es solo una versión simple. Imagínense, si el rango de elementos que se clasificarán es relativamente grande, como 1 ~ 10,000, ¿necesita 10,000 cubos? De hecho, en este caso, un elemento no siempre se coloca en un balde, pero muchas veces se colocan múltiples elementos en un cubo. De hecho, la clasificación real de cubos y la lista hash tienen el mismo principio.
En la clasificación real, los elementos en cada cubo generalmente se clasifican utilizando otros algoritmos de clasificación, por lo que más a menudo, la clasificación de cubos se usa en combinación con otros algoritmos de clasificación.
2. Código de clasificación de cubos
Después de analizar la idea de la clasificación de cubos, primero debe conocer el rango de elementos que se clasificarán. Tomando lo anterior como ejemplo, declare una matriz de longitud 10 como 10 cubos, y luego coloque los resultados uno por uno en el cubo, el valor del cubo es +1 y finalmente emite el subíndice de matriz en orden inverso. El valor de cada posición de la matriz se emite varias veces, de modo que se puede lograr la clasificación básica de cubo.
Public Class BucketSort {private int [] cubos; array private int []; public bucketsort (int rango, int [] array) {this.buckets = new int [range]; this.array = array; } /*Sorting* / public void sort () {if (array! = Null && array.length> 1) {for (int i = 0; i <array.length; i ++) {buckets [array [i]] ++; }}}/*Ordenar la salida*/public void sort () {// Datos de salida invertidos para (int i = buckets.length-1; i> = 0; i-) {for (int j = 0; j <buckets [i]; j ++) {system.print (i+"/t"); }}}}Código de prueba:
public class sorttest {public static void main (string [] args) {testBucketSsort (); } private static void testbucketSsort () {int [] array = {5,7,3,5,4,8,6,4,1,2}; Bucketsort BS = nuevo BucketSort (10, matriz); bs.sort (); bs.sortout (); // sort de impresión de salida}}3. Características de rendimiento de clasificación de cubos
La clasificación de cubos en realidad solo requiere iterarse a través de todos los elementos para ordenarse y luego colocarlos en la posición especificada en secuencia. Si se agrega el tiempo de clasificación de salida, todos los cubos deben atravesarse. Por lo tanto, la complejidad del tiempo de la clasificación de cubos es O (n+m), n es el número de elementos que se clasificarán y M es el número de cubos, es decir, el rango de elementos a clasificar. Este algoritmo es un algoritmo de clasificación muy rápido, pero la complejidad espacial es relativamente grande.
Cuando el rango de tamaño de elementos que se organizará es relativamente grande, pero el número de elementos que se organizarán es relativamente pequeño, los desechos espaciales son más graves. La distribución de elementos a organizar es uniforme cada mes, y cuanto mayor sea la tasa de utilización del espacio, esto es realmente raro.
A través del análisis de rendimiento anterior, podemos obtener las características de la clasificación de cubos: rápido y simple, pero al mismo tiempo, la utilización del espacio es baja. Cuando los datos a ordenar son grandes, la tasa de utilización del espacio es insoportable.
4. Clasificación de cubos escenarios aplicables
Según las características de la clasificación de cubos, la clasificación de cubos generalmente es aplicable a algunos entornos específicos, como el rango de datos es relativamente limitado o hay algunos requisitos específicos, como la necesidad de obtener rápidamente ciertos valores a través del mapeo hash, y el número de cada número debe contar. Pero todo esto se basa en confirmar el alcance de los datos. Si el alcance del alcance es demasiado grande, considere usar otros algoritmos.