En comparación con los algoritmos como la clasificación de burbujas, la clasificación de selección, etc., los principios de algoritmo específicos y la implementación de la clasificación rápida son difíciles. Para comprender mejor la clasificación rápida, todavía describimos los principios algorítmicos de la clasificación rápida en detalle en forma de ejemplos. En el algoritmo de clasificación anterior, utilizaremos el problema de clasificación de altura de 5 atletas como ejemplo para explicarlo. Para reflejar mejor las características de la clasificación rápida, agregaremos 3 atletas más aquí. Los 8 atletas y su información de altura en el ejemplo son los siguientes (F, G, H son nuevos atletas): A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
En el algoritmo de clasificación anterior, el entrenador realizó todas estas clases. Ahora que el número de atletas ha aumentado, el entrenador también quiere aprovechar la oportunidad para tomar un descanso, por lo que el entrenador llamó a dos asistentes y pidió a los dos asistentes que ordenen las alturas de los 8 atletas de izquierda a derecha y baja a alta de una manera rápida.
Según el principio del algoritmo del método de clasificación rápida, los dos asistentes se paran en ambos lados de la disposición del atleta, como se muestra en la figura a continuación:
Primero, el Asistente 1 selecciona un atleta de la disposición (generalmente selecciona el primer atleta en el atleta izquierdo o medio), y aquí selecciona el atleta A (181). Dado que la clasificación es de izquierda a derecha y de baja a alta, el Asistente 1 requiere un atleta que tenga una altura más pequeña que A (181) (la A (181) seleccionada se usa como el punto de referencia para la comparación. Todas las comparaciones en esta ronda se comparan con el atleta A (181)) inicialmente seleccionado):
Continuemos para referirnos al diagrama detallado de la primera ronda de clasificación rápida.
Cuando los dos asistentes se reúnen durante el proceso de clasificación y búsqueda, se detiene la comparación de la ronda actual y el atleta inicialmente seleccionado A (181) se coloca en el espacio vacío donde se encuentran los dos asistentes:
En rápido tipo, esta ronda de clasificación termina cuando dos asistentes se encuentran. En este momento, encontramos que el uso de la posición A (181) donde los dos atletas se reunieron como punto de división, los de la izquierda son atletas que son más pequeños que un (181), y los de la derecha son atletas que son más grandes que un (181). En este momento, separaremos los dos tipos en el lado izquierdo y derecho de un (181). Si continuamos ordenando los arreglos en ambos lados utilizando los métodos de clasificación de los dos asistentes anteriores, luego, después de múltiples arreglos, finalmente obtendremos los resultados de clasificación que necesitamos.
Lo anterior es todo el proceso de implementación de clasificación de clasificación rápida. La clasificación rápida es utilizar las reglas de clasificación anteriores para dividir un arreglo en dos arreglos, y los dos arreglos en cuatro arreglos hasta que no hay un acuerdo para dividirse, y finalmente obtenemos el resultado de clasificación que necesitamos.
Ahora, todavía programamos el código Java para ordenar las alturas de los 8 atletas anteriores usando el orden rápido:
/*** Clasificación rápida de los elementos en la matriz especificada de inicio a finalización** @param matriz La matriz especificada* @param inicia el punto resultante de la consulta de la matriz que debe ordenarse rápidamente* @param finalizar el final del índice de la matriz que debe ordenarse rápidamente*/public estatic final rápido (int [] mate intrain equivalente a la posición del asistente 2 int i = inicio, j = end; int pivot = array [i]; // Tome el primer elemento como el elemento de referencia int vacíaindex = i; // se indica el índice de posición del espacio vacío, y el valor predeterminado es la posición del elemento de referencia que se está recuperando // Si hay más de 1 elementos para clasificar, ingrese la clasificación rápida (siempre que yo y J sean diferentes, significa que al menos 2 elementos de matriz deben ser clasificados) mientras (i <j) {// Asistente 2 2 busca elementos más pequeños de lo que el elemento de referencia de la derecha a la izquierda (i <j & pivot <= arshay J]; if (i <j) {// Si el asistente 2 encuentra el elemento correspondiente antes de encontrar el asistente 1, le da el elemento a las "vacantes" del asistente 1, j se convierte en una matriz espacial vacía [vacíaindex] = array [vacíaindex = j]; } // Asistente 1 comienza a buscar elementos más grandes que el elemento de referencia de izquierda a derecha (i <j && array [i] <= pivot) i ++; if (i <j) {// Si el Asistente 1 encuentra el elemento correspondiente antes de encontrar el Asistente 2, le dará el elemento a las "vacantes" del Asistente 2, y me convierte en una matriz vacante [vacíaindex] = array [vacíaintex = i]; }} // Después del encuentro del Asistente 1 y Asistente 2, el bucle se detendrá y el valor de referencia inicial se lleva a la última matriz vacante [vacíaindex] = pivot; // ===== Esta ronda de clasificación rápida se completa ====== // Si hay más de 2 elementos en el lado izquierdo del punto de división I, la llamada recursiva continúa clasificándola rápidamente si (i - inicio> 1) {Quicksort (matriz, 0, i - 1); } // Si hay más de 2 elementos en el lado derecho del punto de división J, la llamada recursiva continúa ordenándolo rápidamente si (end - j> 1) {Quicksort (Array, j + 1, end); }} // Método principal Public static void main (string [] args) {// ===== Sort de bajo a alto usando el método de clasificación rápida para representar las alturas de 8 atletas ====== // A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182) int [] Heaths 187, 172, 163, 191, 189, 182}; // Llame al método de clasificación rápida Quicksort (Heights, 0, Heights.length - 1); // resultado ordenado de salida para (int altura: alturas) {system.out.println (altura); }}Los resultados de ejecución del código Java anteriores se emiten de la siguiente manera:
163169172181182187189191
Nota: Debido a las diferencias de pensamiento local, puede haber múltiples variaciones en la implementación del código clasificado rápido anterior. Sin embargo, no importa qué variantes sean, la idea central de la clasificación rápida no cambiará.
Otra implementación: escaneo unidireccional
Hay otra versión de escaneo unidireccional para la cortación de matriz de clasificación rápida. El paso específico es seleccionar el último elemento en la matriz como elemento de corte y establecer dos punteros. El puntero I apunta a una posición frente al primer elemento en la matriz, y J apunta al primer elemento en la matriz. J escanea de adelante hacia la derecha y la derecha. Cuando se encuentre con un elemento de corte menos o igual, agregue i a uno e intercambie los elementos señalados por I y J. Finalmente, intercambie los elementos en la posición I+1 y los elementos de corte para completar la división de matriz. La implementación del código es la siguiente:
int partition (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hola); regresar i + 1;}