Un tipo de mejora en la clasificación burbujeante es que si la secuencia de registro inicial es ordenada o básicamente ordenada por palabras clave, se degenerará en la clasificación burbujeante. Se utiliza el principio de recursión, y su rendimiento promedio es el mejor entre todos los métodos de clasificación del mismo orden de magnitud o (n longn). En términos de tiempo promedio, actualmente se considera el mejor método de clasificación interna.
La idea básica es: divide los datos que se clasificarán en dos partes independientes mediante la clasificación, y todos los datos en parte son más pequeños que todos los datos en la otra parte, y luego ordene rápidamente estas dos partes de los datos de acuerdo con este método .
Tres punteros: el primer puntero se llama Pivotkey Pointer (Pivot), el segundo puntero y el tercer puntero son el puntero y el puntero derecho, respectivamente, apuntando al valor más a la izquierda y al valor más derecho. El puntero izquierdo y el enfoque del puntero derecho desde ambos lados hasta el medio al mismo tiempo. Pivote al extremo superior.
Se requieren dos funciones:
① Función recursiva Public static void Quicksort (int [] n, int a la izquierda, int derecha)
② Función de segmento (una función de clasificación rápida) public static int Partition (int [] n, int izquierdo, int correcto)
Código fuente de Java (ejecute correctamente):
La copia del código es la siguiente:
Paquete TestSortalgorithm;
Clase pública Quicksort {
public static void main (string [] args) {
int [] array = {49,38,65,97,76,13,27};
Quicksort (matriz, 0, array.length - 1);
para (int i = 0; i <array.length; i ++) {
System.out.println (Array [i]);
}
}
/*Primero escriba el algoritmo como el prototipo de datos según la matriz, y luego escriba el algoritmo de escalabilidad. Array {49,38,65,97,76,13,27}
* */
public static void Quicksort (int [] n, int izquierdo, int right) {
int pivot;
if (izquierda <derecha) {
// Pivote Como pivote, el elemento más pequeño está a la izquierda y el elemento más grande está a la derecha
pivot = partición (n, izquierda, derecha);
// Llame recursivamente a la clasificación rápida en las matrices izquierda y derecha hasta que el pedido esté completamente correcto
Quicksort (n, izquierda, pivote - 1);
Quicksort (n, pivote + 1, derecha);
}
}
Public static int Partition (int [] n, int izquierdo, int right) {
int pivotkey = n [izquierda];
// El pivote nunca cambiará después de ser seleccionado, y eventualmente estará en el medio, con una pequeña parte delantera y una parte posterior grande
while (izquierdo <derecho) {
while (izquierda <derecha && n [derecha]> = pivotkey) -right;
// Mueve el elemento más pequeño que el pivote al extremo inferior.
n [izquierda] = n [derecha];
while (izquierda <derecha && n [izquierda] <= pivotkey) ++ izquierda;
// Mueve el elemento más grande que el pivote al extremo superior.
n [derecha] = n [izquierda];
}
// Cuando a la izquierda == a la derecha, complete un viaje de clasificación rápido.
n [izquierda] = pivotkey;
regresar a la izquierda;
}
}