El algoritmo de clasificación se utiliza en muchos lugares. Recientemente revisé el algoritmo nuevamente y lo implementé yo mismo. Lo registraré aquí y guardaré algo de material para revisarlo en el futuro.
Sin más preámbulos, echemos un vistazo a los algoritmos de clasificación clásicos uno por uno:
1. Seleccione ordenar
La idea básica de la clasificación por selección es que durante el proceso de atravesar la matriz, si i representa el número de secuencia actual que debe ordenarse, debe encontrar el valor mínimo entre los [i...n-1] restantes. y luego apunte el valor mínimo encontrado a i se intercambian los valores. Debido a que cada proceso de determinación de elementos tendrá un subproceso de selección del valor máximo, la gente lo llama vívidamente clasificación por selección. Tomemos un ejemplo:
Inicial: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0º [38]<->8º [2])
i = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1.º [38]<->4.º [17])
i = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2º [11]<->9º [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (no se requiere intercambio)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4to [17]<->9no [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5º [31]<->9º [17])
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6º [39]<->9º [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no se requiere intercambio)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no se requiere intercambio)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (no se requiere intercambio)
Como se puede ver en el ejemplo, a medida que avanza la clasificación por selección (i aumenta gradualmente), el número de comparaciones será cada vez menor. Sin embargo, independientemente de si la matriz está ordenada inicialmente o no, la clasificación por selección realizará una comparación de selección. desde i hasta el final de la matriz, entonces, para una matriz de longitud determinada, el número de comparaciones en la clasificación por selección es fijo: 1 + 2 + 3 +… + n = n * (n + 1) / 2. Y el número de intercambios está relacionado con el orden de la matriz inicial. Si el orden de la matriz inicial es aleatorio, entonces, en el peor de los casos, los elementos de la matriz se intercambiarán n veces y, en el mejor de los casos, puede ser 0 veces (. la matriz en sí es secuencia).
Se puede deducir que la complejidad temporal y espacial de la clasificación por selección son O (n2) y O (1) respectivamente (la clasificación por selección solo requiere un espacio adicional para el intercambio de elementos de la matriz).
Código de implementación:
Copie el código de código de la siguiente manera:
/**
*Clasificación de selección
*/
SELECCIÓN(nueva Ordenable() {
public <T extiende Comparable<T>> void sort(T[] matriz, ascenso booleano) {
int len = matriz.longitud;
para (int i = 0; i < len; i++) {
int seleccionado = i;
para (int j = i + 1; j < len; j++) {
int comparar = matriz[j].compareTo(matriz[seleccionado]);
if (comparar != 0 && comparar < 0 == ascender) {
seleccionado = j;
}
}
intercambio(matriz, i, seleccionado);
}
}
})
2. Ordenación por inserción
La idea básica de la ordenación por inserción es que durante el proceso de atravesar la matriz, suponiendo que los elementos antes del número de serie i, es decir [0..i-1], se hayan ordenado, este viaje debe encontrar la posición correcta. k del elemento x correspondiente a i, y En el proceso de encontrar esta posición k, los elementos comparados se mueven hacia atrás una posición uno por uno para "hacer espacio" para el elemento x. Finalmente, se asigna el valor del elemento correspondiente a k. x. La clasificación por inserción también se denomina según las características de la clasificación.
El siguiente es un ejemplo. Los números marcados en rojo son números insertados. Los números tachados son elementos que no participan en esta clasificación. Los elementos entre los números marcados en rojo y los números tachados son elementos que se mueven hacia atrás. uno por uno, como Los elementos que participan en la segunda clasificación son [11, 31, 12], y el elemento que debe insertarse es 12, pero 12 no está actualmente en la posición correcta, por lo que debemos insertarlo con los elementos anteriores 31 y 11 en secuencia. Compare, mueva los elementos comparados mientras compara y deje de comparar cuando encuentre el primer elemento 11 que sea menor que 12. En este momento, el índice 1 correspondiente a 31 es la posición donde se debe insertar 12.
Inicial: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Primera pasada: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (sin elementos movidos)
Segundo viaje: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 retrocede)
Tercer viaje: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 todos retroceden)
Cuarto pase: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (sin elementos móviles)
Quinto viaje: [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 retrocede)
El sexto viaje: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 retrocede)
La séptima pasada: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (sin elementos móviles)
Octavo viaje: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 movimientos hacia atrás)
Noveno viaje: [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 retrocediendo)
La clasificación por inserción es mejor que la clasificación por selección porque puede aprovechar el hecho de que la primera parte de los elementos de la matriz se ha ordenado durante el proceso de clasificación, lo que reduce efectivamente el número de comparaciones. Por supuesto, esta ventaja depende del orden inicial de las comparaciones. array. Al final, en el mal caso (la matriz dada está en orden inverso), el número de comparaciones y movimientos necesarios para la ordenación por inserción será igual a 1 + 2 + 3... + n = n * (n). + 1) / 2. En este caso extremo, la clasificación por inserción La eficiencia de la clasificación es incluso peor que la clasificación por selección. Por lo tanto, la clasificación por inserción es un método de clasificación inestable y la eficiencia de la inserción está estrechamente relacionada con el orden inicial de la matriz. En general, la complejidad temporal y espacial del tipo de inserción son O (n2) y O (1) respectivamente.
Código de implementación:
Copie el código de código de la siguiente manera:
/**
*Clasificación por inserción
*/
INSERCIÓN(nueva Ordenable() {
public <T extiende Comparable<T>> void sort(T[] matriz, ascenso booleano) {
int len = matriz.longitud;
para (int i = 1; i < len; i++) {
T toInsert = matriz[i];
int j = yo;
para (; j > 0; j) {
int comparar = matriz[j - 1].compareTo(toInsert);
if (comparar == 0 || comparar < 0 == ascender) {
romper;
}
matriz[j] = matriz[j - 1];
}
matriz[j] = toInsert;
}
}
})
3. Clasificación de burbujas
La clasificación de burbujas puede considerarse como el algoritmo de clasificación más clásico. Recuerdo que este algoritmo fue el primero que encontré cuando estaba en la escuela. Debido a que el método de implementación es el más simple, es un bucle for de dos niveles. En el bucle interno, se juzga si dos elementos adyacentes están en orden inverso. Si es así, intercambie los dos elementos y realice un bucle externo para "flotar" el elemento más pequeño entre los elementos restantes en la matriz hacia el frente, así se llama. clasificación de burbujas.
Pongamos un ejemplo sencillo como siempre:
Estado inicial: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
El primer viaje de la capa interna: [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9.° [23]<->8.° [38)
Segunda pasada de la capa interior: [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8.º [23]<->7.º [29])
La tercera pasada de la capa interna: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7.° [23]<->6.° [31])
La cuarta pasada de la capa interna: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 y 23 están todos en el orden correcto, no se requiere intercambio)
El quinto viaje de la capa interna: [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5to [7]<->4to [36])
El sexto viaje de la capa interna: [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4to [7]<->3ro [39])
La séptima pasada de la capa interna: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3.° [7]<->2.° [26])
La octava pasada de la capa interior: [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2.º [7]<->1.º [19])
El noveno viaje de la capa interior: [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1.º [7]<->0.º [24])
……….
De hecho, la clasificación por burbujas es similar a la clasificación por selección. El número de comparaciones es el mismo, n * (n + 1) / 2. Sin embargo, la clasificación por burbujas realizará intercambios adicionales en el proceso de selección del valor mínimo (la clasificación por burbujas solo necesita). Si se descubre que el orden de los elementos adyacentes no es correcto, se intercambiarán. En consecuencia, la clasificación por selección solo decidirá si se intercambia de acuerdo con la situación después de que se complete la comparación del bucle interno), por lo que, en mi opinión, la clasificación por selección pertenece. para clasificar burbujas. Versión mejorada.
Código de implementación:
Copie el código de código de la siguiente manera:
/**
* Clasificación por burbujas, es muy similar a la Clasificación por inserción
*/
BURBUJA(nueva Ordenable() {
public <T extiende Comparable<T>> void sort(T[] matriz, ascenso booleano) {
int longitud = matriz.longitud;
int últimoIdx intercambiado = 0;
para (int i = 0; i < longitud; i++) {
// marca la bandera para identificar si el intercambio fue falso
booleano isExchanged = falso;
// la última comparación e intercambio ocurrió antes de alcanzar el índice i
int currOrderedIdx = últimoIdxExchanged > i ? últimoIdxExchanged: i;
for (int j = longitud 1; j > currOrderedIdx; j) {
int comparar = matriz[j - 1].compareTo(matriz[j]);
if (comparar != 0 && comparar > 0 == ascender) {
intercambio(matriz, j 1, j);
isExchanged = verdadero;
últimoExchangedIdx = j;
}
}
// si no ocurre ningún intercambio significa que la matriz ya está en orden
si (isExchanged == falso) {
romper;
}
}
}
})
4. Clasificación de colinas
La clasificación Hill nació porque la clasificación por inserción encontró el problema de mover demasiados elementos cuando se trataba de matrices grandes. La idea de la clasificación Hill es "dividir y conquistar" una matriz grande en varias matrices pequeñas, divididas por espacios, como la matriz [1, 2, 3, 4, 5, 6, 7, 8]. = 2 para dividir, se puede dividir en dos matrices [1, 3, 5, 7] y [2, 4, 6, 8] (en correspondencia, como brecha = 3 , entonces las matrices divididas son: [1, 4, 7], [2, 5, 8], [3, 6]) Luego realice la clasificación por inserción en las matrices divididas y luego redúzcalas después de ordenar cada submatriz. Repita los pasos anteriores hasta que la brecha = 1 , es decir, la clasificación por inserción se realiza en toda la matriz. En este momento, la matriz está básicamente ordenada, por lo que los elementos que deben moverse serán muy pequeños, lo que resuelve el problema de más movimientos en la clasificación por inserción cuando se procesan grandes. matrices de escala.
Consulte la clasificación por inserción para ver ejemplos específicos.
Hill sort es una versión mejorada de la clasificación por inserción. Es muy útil para mejorar la eficiencia cuando la cantidad de datos es grande. Cuando la cantidad de datos es pequeña, se recomienda utilizar la clasificación por inserción directamente.
Código de implementación:
Copie el código de código de la siguiente manera:
/**
* Clasificación de conchas
*/
SHELL(nueva Ordenable() {
public <T extiende Comparable<T>> void sort(T[] matriz, ascenso booleano) {
int longitud = matriz.longitud;
brecha interna = 1;
// usa el más próximo a la longitud / 3 como primer espacio
mientras (espacio < longitud / 3) {
brecha = brecha * 3 + 1;
}
mientras (brecha >= 1) {
for (int i = espacio; i < longitud; i++) {
T siguiente = matriz[i];
int j = yo;
mientras (j >= espacio) {
int comparar = matriz[j - brecha].compareTo(siguiente);
// ya encontré su posición
if (comparar == 0 || comparar < 0 == ascender) {
romper;
}
matriz[j] = matriz[j - espacio];
j -= brecha;
}
si (j != i) {
matriz[j] = siguiente;
}
}
brecha /= 3;
}
}
})
5. Combinar clasificación
La clasificación por combinación se implementa mediante recursividad, que es un método de "divide y vencerás". La matriz de destino se divide en dos desde la mitad y luego las dos matrices se clasifican por separado. Una vez completada la clasificación, las dos matrices ordenadas se "fusionan". "En Juntos, lo más importante de la clasificación por combinación es el proceso de "fusión". El proceso de combinación requiere espacio adicional que sea consistente con la longitud de las dos matrices que deben fusionarse. Por ejemplo, las matrices que deben especificarse son: [3, 6, 8, 11] y [1, 3, 12, 15] (aunque lógicamente están divididos en dos matrices, estos elementos en realidad todavía están en la matriz original, pero están divididos en dos matrices a través de algunos índices. La matriz original para [3, 6, 8, 11, 1, 3, 12, 15, configuramos tres punteros bajo, medio y alto en 0, 3 y 7 respectivamente. Se puede lograr una división lógica de subarreglos) Entonces la longitud del arreglo adicional requerido es 4 + 4 = 8. El proceso de fusión se puede resumir brevemente de la siguiente manera:
1) Copie los elementos de las dos submatrices a la nueva matriz copyArray. Tome el ejemplo mencionado anteriormente como ejemplo, copyArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) Configure dos punteros para que apunten al primer elemento correspondiente en la matriz atómica respectivamente. Suponga que los dos punteros se denominan leftIdx y rightIdx, luego leftIdx = 0 (correspondiente al primer elemento [3] en copyArray), rightIdx = 4 ( correspondiente al quinto elemento [1] en copyArray);
3) Compare los valores de los elementos de la matriz señalados por leftIdx y rightIdx, seleccione el más pequeño y asigne su valor a la posición correspondiente i en la matriz original. Una vez completada la asignación, realice una operación de incremento automático en el. dos índices que participan en la asignación. Si el valor leftIdx o rigthIdx ha llegado al final de la matriz correspondiente, todo lo que queda es copiar los elementos restantes de la matriz en las posiciones restantes en orden.
A continuación se muestra un ejemplo específico de fusión:
Primer viaje:
Matriz auxiliar [21, 28, 39 | 35, 38] (la matriz se divide en dos submatrices izquierda y derecha, separadas por |)
[21, , , , ] (La primera vez que se compara 21 con 35, gana el subarreglo izquierdo, leftIdx = 0, i = 0)
Segundo viaje:
Matriz auxiliar [21, 28, 39 |
[21, 28, , , ] (La segunda vez que se compara 28 con 35, gana el subarreglo izquierdo, leftIdx = 1, i = 1)
Tercer viaje: [21, 28, 39 |
[21, 28, 35, , ] (La tercera vez que se compara 39 con 35, gana el subarreglo derecho, rightIdx = 0, i = 2)
El cuarto viaje: [21, 28, 39 |
[21, 28, 35, 38,] (La cuarta vez que se comparan 39 y 38, gana el subarreglo derecho, rightIdx = 1, i = 3)
El quinto viaje: [21, 28, 39 |
[21, 28, 35, 38, 39] (La submatriz derecha se ha copiado por quinta vez, no es necesario comparar leftIdx = 2, i = 4)
Lo anterior es un proceso de fusión. Podemos dividir la matriz completa que debe ordenarse un número limitado de veces (dividida en dos cada vez) hasta que se divida en una matriz pequeña con una longitud de 1. Cuando la longitud es 1, ya no es necesario ordenar la matriz. Después de eso, estas matrices se fusionan en orden inverso (debido a la recursión) hasta que se fusiona el último subarreglo de longitud n/2. Una vez completada la fusión, también se completa la clasificación de la matriz.
La clasificación por combinación requiere la mayor cantidad de espacio adicional de todas las clasificaciones, y cada combinación requiere la misma cantidad de elementos que la suma de las longitudes de las dos matrices que participan en la combinación (para proporcionar una matriz auxiliar). Entonces se puede inferir que la complejidad espacial de la ordenación por fusión es 1 + 2 + 4 + ... + n = n * (n + 2) / 4 (ignorando el juicio de paridad de n. La complejidad temporal es difícil de estimar). Aquí también olvidé cuántos ().
Código de implementación:
Copie el código de código de la siguiente manera:
/**
* Combinar clasificación
*/
FUSIONAR(nueva Ordenable() {
public <T extiende Comparable<T>> void sort(T[] matriz, ascenso booleano) {
this.sort(matriz, 0, matriz.longitud 1, ascender);
}
privado <T extiende Comparable<T>> void sort(T[] matriz, int lo, int hi, boolean ascend) {
// OPTIMIZAR UNO
// si la longitud de la subcadena es menor que 20,
// usa ordenación por inserción para reducir la invocación recursiva
si (hola lo < 20) {
para (int i = lo + 1; i <= hola; i++) {
T toInsert = matriz[i];
int j = yo;
para (; j > lo; j) {
int comparar = matriz[j - 1].compareTo(toInsert);
if (comparar == 0 || comparar < 0 == ascender) {
romper;
}
matriz[j] = matriz[j - 1];
}
matriz[j] = toInsert;
}
devolver;
}
int medio = bajo + (hola bajo) / 2;
ordenar (matriz, bajo, medio, ascender);
ordenar (matriz, mitad + 1, hola, ascender);
fusionar (matriz, bajo, medio, alto, ascender);
}
privado <T extiende Comparable<T>> void merge(T[] matriz, int lo, int mid, int hi, boolean ascend) {
// OPTIMIZAR DOS
// si ya está en el orden correcto, omite esta combinación
// ya que no es necesario hacerlo
int leftEndCompareToRigthStart = matriz[medio].compareTo(matriz[medio + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascender) {
devolver;
}
@SuppressWarnings("sin marcar")
T[] arrayCopy = (T[]) nuevo Comparable[hola - bajo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int bajoIdx = 0;
int altoIdx = medio bajo + 1;
para (int i = lo; i <= hola; i++) {
si (bajoIdx > medio bajo) {
// submatriz izquierda agotada
matriz[i] = matrizCopy[highIdx++];
} si no (highIdx > hola lo) {
// submatriz derecha agotada
matriz[i] = matrizCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascender) {
matriz[i] = matrizCopy[lowIdx++];
} demás {
matriz[i] = matrizCopy[highIdx++];
}
}
}
})
6. Clasificación rápida
La clasificación rápida también es un algoritmo de clasificación de "divide y vencerás" implementado mediante el método de combinación. Su encanto es que puede determinar la posición final correcta de la clasificación para un elemento de matriz en cada partición (el núcleo del algoritmo de clasificación) (una vez). Si el posicionamiento es preciso, este elemento no será considerado en el siguiente ciclo).