1. Descripción general
La clasificación y la búsqueda son dos problemas muy básicos en la programación, y se utilizan muchos algoritmos clásicos para resolver estos dos tipos de problemas. Este artículo realiza principalmente una discusión básica sobre la implementación de algoritmos de clasificación en Java, con la esperanza de servir como punto de partida. role. Antes de eso, déjame hacerte algunas preguntas: ¿Puedes escribir una clasificación rápida correcta? ¿En qué circunstancias la clasificación rápida es realmente rápida? ¿Su cola rápida es lo suficientemente rápida? ¿Se puede optimizar aún más? Con estas preguntas, echemos un vistazo a cómo se implementa la clasificación rápida en jre7.
La clase de implementación de clasificación en Jre7 es DualPivotQuickSort.java. En comparación con jre6, hay algunos cambios, principalmente en dos lugares: uno es la implementación de la clasificación por inserción y el otro es que el pivote en la implementación de QuickSort cambia de uno a dos. . Tomemos como ejemplo una matriz de tipo int. Hay un método central para la implementación de clasificación en esta clase.
Copie el código de código de la siguiente manera:
clasificación vacía (int [] a, int izquierda, int derecha, booleano más a la izquierda)
El parámetro a es la matriz que debe ordenarse, la izquierda representa el índice del elemento más a la izquierda en el rango de la matriz que debe ordenarse, la derecha representa el índice del elemento más a la derecha en el rango y la más a la izquierda representa si el rango es el más a la izquierda. rango en la matriz. Por ejemplo:
Matriz: [2, 4, 8, 5, 6, 3, 0, -3, 9] se puede dividir en tres intervalos (2, 4, 8) {5, 6} <3, 0, -3, 9>
Para el intervalo (), izquierda = 0, derecha = 2, extremo izquierdo = verdadero
Para el intervalo {}, izquierda = 3, derecha = 4, extremo izquierdo = falso, los parámetros correspondientes del intervalo <> se pueden obtener de la misma manera.
Cuando la longitud del intervalo es inferior a 47, este método utilizará la clasificación por inserción; de lo contrario, se utilizará la clasificación rápida.
2. Implementación de ordenación por inserción.
Cuando el extremo izquierdo es verdadero, se utilizará la clasificación de inserción tradicional y el código es relativamente simple. El proceso es similar a agarrar e insertar cartas cuando se juega a las cartas:
Copie el código de código de la siguiente manera:
for (int i = izquierda, j = i; i < derecha; j = ++i) {
int ai = a[i + 1];
mientras (ai < a[j]) {
a[j + 1] = a[j];
si (j-- == izquierda) {
romper;
}
}
a[j + 1] = ai;
}
Código de clasificación de inserción tradicional
Cuando el extremo izquierdo es falso, utiliza un nuevo tipo de ordenación por inserción (ordenación por inserción de pares). La mejora es que cada vez que atraviesa la matriz previamente ordenada, se deben insertar dos elementos, mientras que la ordenación por inserción tradicional solo requiere encontrar una ubicación adecuada para. un elemento para insertar. Para la clasificación por inserción, la clave es encontrar una posición de inserción adecuada para el elemento a insertar. Para encontrar esta posición, es necesario atravesar el subarreglo previamente ordenado, por lo que para la clasificación por inserción, los elementos que atraviesa durante toda la clasificación. proceso El número determina su rendimiento. Obviamente, insertar dos elementos en cada recorrido puede reducir la cantidad de elementos atravesados durante el proceso de clasificación. El código de implementación es el siguiente:
Copie el código de código de la siguiente manera:
for (int k = izquierda; ++izquierda <= derecha; k = ++izquierda) {
int a1 = a[k], a2 = a[izquierda];
si (a1 < a2) {
a2 = a1; a1 = a[izquierda];
}
mientras (a1 < a[--k]) {
un[k + 2] = un[k];
}
a[++k + 1] = a1;
mientras (a2 < a[--k]) {
un[k + 1] = un[k];
}
a[k + 1] = a2;
}
Ahora surge una pregunta: ¿Por qué el rango más a la izquierda usa el orden de inserción tradicional y los demás usan el orden de inserción por pares? ¿Qué problemas surgirán si reemplazamos el código de clasificación de inserción tradicional con el código de clasificación de inserción por pares anterior? Espero que todos ustedes mismos lo respondan. . .
3. Implementación de clasificación rápida
La clasificación rápida también se ha mejorado en Jre7. La clasificación rápida tradicional selecciona un pivote (los métodos de jre6 para seleccionar un pivote son seleccionar los elementos en las posiciones más a la izquierda, media y derecha de la matriz, y clasificar los elementos con los valores medios como. pivote), y luego atravesar desde ambos extremos hasta el medio, y colocar los objetos encontrados durante el recorrido izquierdo El valor mayor que el pivote se intercambia con el valor menor o igual que el pivote encontrado en el recorrido de la derecha. Cuando el recorrido se encuentra, se inserta el valor del pivote, esto hace que los valores a la izquierda del pivote sean menores que o; igual a pivote, y el valor a la derecha de pivote es mayor que pivote continuar A continuación, use la recursividad para ordenar los lados izquierdo y derecho respectivamente;
A través del análisis anterior, podemos ver que: cada paso de la ordenación por inserción es hacer un subrango de la matriz absolutamente ordenado, y la esencia de cada ciclo es expandir continuamente este subrango, por lo que podemos ver que la dirección de optimización es make Cada recorrido de bucle hace que el subrango se expanda lo más rápido posible, por lo que se optimiza la optimización anterior de insertar un elemento por recorrido para insertar dos elementos a la vez. Por supuesto, alguien definitivamente preguntará: ¿por qué no aumentar este número? Por ejemplo, se insertan 5 o 10 cada vez que se recorre. . . Obviamente, esto no es posible. Un caso extremo es insertar n elementos (n es la longitud de la matriz) cada vez que se recorre. . . En cuanto a por qué, todos pueden responder por sí mismos.
Para la clasificación rápida, lo que hace cada recursión es hacer que los subrangos que deben ordenarse se vuelvan más ordenados, en lugar de absolutamente ordenados; por lo tanto, para la clasificación rápida, su rendimiento depende de cómo cada operación recursiva hace que el subrango que se va a ordenar sea más ordenado. El determinante del grado en que se ordena un subintervalo es, por supuesto, el número de recursiones. La clave para una clasificación rápida para que el subintervalo sea relativamente ordenado es el pivote, por lo que la dirección de nuestra optimización también debe ser el pivote. Luego, aumente el número de pivotes y podemos encontrar que aumentar el número de pivotes no afecta el número de pivotes. recursiones. Tendrá un gran impacto y, a veces, incluso puede reducir el número de recursiones. Una pregunta similar a la ordenación por inserción es: ¿cuántos pivotes se deben aumentar? Obviamente, el valor del pivote no puede ser demasiado grande; recuerde, cualquier optimización tiene un costo, y el costo de aumentar el pivote está oculto en el proceso de intercambiar la posición de los elementos cada vez. Guanzi parece venderse demasiado. . . Echemos un vistazo a qué tan rápida se implementa la clasificación cuando el valor de pivote es 2. En realidad, su proceso de implementación no es difícil de entender:
1. Primero seleccione dos pivotes. El método de selección de pivotes consiste en dividir la matriz en seis segmentos de igual longitud. Estos seis segmentos en realidad están separados por 5 elementos. 4º, como pivote1 y pivot2 respectivamente;
2. Después de seleccionar Pivote, recorra desde los extremos izquierdo y derecho hasta el centro. La condición de parada para el recorrido izquierdo es encontrar un valor mayor o igual a pivot1 y marque esa posición como menor; El recorrido es encontrar un valor menor o igual al valor de pivot2 y marcar esa posición como grande.
3. Luego recorra hacia atrás desde la posición menor. La posición atravesada está representada por k. Encontrará las siguientes situaciones:
a. Si el valor de la posición k es menor que pivot1, entonces intercambie los valores de la posición k y la posición menor, y agregue 1 al valor de menor, esto hará que los valores estén a la izquierda de la posición. La posición menor es menor que pivot1, y los valores entre la posición menor y la posición k serán mayores o iguales que pivot1.
b. Si el valor en la posición k es mayor que pivot2, entonces recorra desde la gran posición hacia la izquierda. La condición de parada para el recorrido es encontrar un valor menor o igual que pivot2. Si este valor es menor que pivot1. este valor en la posición menor y escriba el valor en la posición menor. El valor se escribe como la posición k y el valor de la posición k se escribe como la posición mayor, y finalmente menor++, excelente--; para ser mayor o igual que pivot1, intercambie la posición k y la gran posición, y luego gran-
4. Después de completar el proceso anterior, el subintervalo ordenado se divide en tres segmentos (<pivot1, pivot1<=&&<=pivot2,>pivot2). Finalmente, se utiliza la recursividad para estos tres segmentos.
Copie el código de código de la siguiente manera:
/*
*Partición:
*
* parte izquierda parte central parte derecha
* +------------------------------------------------ ---------------+
* | <pivote1 | pivote1 <= && <= pivote2 |
* +------------------------------------------------ ---------------+
* ^ ^ ^
* |
* menos k genial
*
*Invariantes:
*
* todo dentro (izquierda, menos) <pivote1
* pivot1 <= todo en [menos, k) <= pivot2
* todo dentro (genial, derecha) > pivot2
*
* El puntero k es el primer índice de la parte ?.
*/
El contenido principal de la implementación de clasificación en Jre7 es el mencionado anteriormente. Para obtener detalles específicos, consulte el código de la clase correspondiente. Si encuentra algún error o insuficiencia, corríjalo.