Quick Sort es un tipo de intercambio de división propuesto por Crahoare en 1962. La idea básica de este método es:
1. Primero tome un número de la secuencia como el número de referencia.
2. En el proceso de partición, ponga todos los números más grandes que este número a su derecha, y todos los números más pequeños que o igual a su izquierda.
3. Repita el segundo paso para los intervalos izquierdo y derecho hasta que solo haya un número en cada intervalo.
El algoritmo tiene una idea clara, pero si el valor límite no se maneja bien durante el proceso de división de intervalo, es fácil causar errores. Los siguientes son dos pensamientos más claros para guiar la escritura del código de división de intervalo.
El primer tipo de pensamiento es el llamado pensamiento del método de excavación en boxes. Lo siguiente es analizar el proceso del método de excavación en boxes analizando un ejemplo:
Tomando una matriz como ejemplo, tome el primer número en el intervalo como número de referencia.
Inicialmente, izquierda = 0; derecho = 9; X = a [izquierda] = 72
Dado que el número en un [0] se ha guardado en X, se puede entender como cavar un agujero en la matriz A [0], y otros datos se pueden llenar aquí.
Comience desde la derecha y busque una serie de <= x. Obviamente, cuando está correcto = 8, si las condiciones se cumplen, excave un [8] y llénelo en el pozo anterior A [izquierda]. Tal pozo A [0] está resuelto, pero se forma un nuevo pozo a [8]. ¿Qué tengo que hacer? Simple, encuentre el número para llenar el pozo A [8]. Esta vez, comience desde la izquierda y encuentre un número mayor que X. Cuando a la izquierda = 3, cumpla con las condiciones, destaque un [3] y llénelo en el pozo anterior A [derecha];
La matriz se convierte en:
Repita los pasos anteriores y la matriz final se convertirá en el siguiente formulario:
Se puede ver que los números antes de un [5] son más pequeños que él, y los números después de un [5] son más grandes que él. Llenar X en el pozo de un [5] y los datos se convierten en:
Por lo tanto, repita los pasos anteriores para los dos subintervalos a [0 ... 4] y a [6 ... 9].
Resumen del número de agujeros
1. I = l; j = r; Excave el número de referencia para formar el primer pozo a [i].
2. J-Desde el reverso al frente, encuentre el número más pequeño que este, destaque este número y complete el pozo anterior A [i].
3. I ++ encuentra un número más grande que este de adelante hacia atrás, y después de encontrarlo, destaque este número y llénelo en el pozo anterior a [j].
4. Repita los pasos 2 y 3 hasta i == j, y complete el número de referencia en un [i].
Siga este método de partición, el código Java se clasifica rápidamente de la siguiente manera:
Partición de clase pública { / ** * Basado en la división base, la pequeña está a la izquierda y la grande está a la derecha, y no se requiere que la secuencia completa se ordene * * @param ary * @param base * / static void sort (int [] ary, int base) {int lefa = 0; int right = ary.length - 1; int LeftPoint = Izquierda, RightPoint = Right; mientras (verdadero) {// divide hacia la izquierda y la derecha a la derecha al mismo tiempo para comparar, de izquierda a derecha, mientras (LeftPoint <derecho && ary [LeftPoint ++] <base); // El punto de izquierda es mayor que el derecho o ary [LeftPoint]> Base Stops Looping While (RightPoint> = Left && Ary [RightPoint--]> base); // en el contrario System.out.println ("el índice que debe intercambiarse a la izquierda:" + (LeftPoint-1)); System.out.println ("El índice que debe intercambiarse a la derecha:"+ (punto de derecha+ 1)); // Los dos índices que no cumplen con las condiciones se obtienen anteriormente, es decir, los dos índices que deben intercambiarse si (LeftPoint - 1 <RightPoint + 1) {// Swap (Ary, LeftPoint - 1, RightPoint + 1); Util.printarray (ary); punto izquierdo = izquierda; punto de la derecha = derecho; } else {break; }}} private static void swap (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main (string [] args) {int [] ary = util.GenerateInTarray (10); System.out.println ("Secuencia original:"); Util.printarray (ary); ordenar (ary, 5); System.out.println ("Ordenado:"); Util.printarray (ary); }} resultado:
Secuencia original: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] Índice para intercambiar a la izquierda: 1 Índice para intercambiar a la derecha: 8 [2, 0, 4, 3, 7, 5, 5, 1, 9, 8, 6] Índice para intercambiar en el índice de la izquierda: 4 Índice a la derecha: 6 [2, 0, 4, 3, 1, 5, 7, 9, 6, 6] Intercambio a la izquierda: Índice de la izquierda a la derecha: 5 a la derecha: 5 a la derecha: 5. Clasificación: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
Otro pensamiento guía en la división de intervalos:
Use el primer elemento de la matriz como valor de intervalo, divídelo desde el segundo elemento hasta que se forme el resultado que se muestra en la figura.
Luego intercambie los valores límite derecho y t del intervalo L <t para formar el siguiente resultado:
De esta manera, puede escribir un código de clasificación rápido de la siguiente manera:
public void QSort (int Array [], int izquierdista, int right) {if (izquierda <derecha) {int key = array [izquierda]; int high = correcto; int lo bajo = izquierda+1; while (true) {while (low <= high && array [low] <= key) Low ++; while (bajo <= high && array [high]> = key) high--; if (bajo> alto) ruptura; intercambio (matriz, bajo, alto); } swap (matriz, izquierda, alto); printArray (matriz); Qsort (matriz, izquierda, alta-1); Qsort (matriz, alto+1, derecha); }}