La clasificación rápida se utiliza ampliamente como algoritmo de clasificación eficiente. El método Arrays.sort en el JDK de SUN utiliza la clasificación rápida.
Quick Sort adopta la idea clásica de dividir y conquistar:
Dividir: seleccione una X primitiva (generalmente el primer elemento de la matriz) y divida la matriz en dos partes mediante alguna operación de partición: la mitad izquierda es menor o igual a X y la mitad derecha es mayor o igual a X. .
Conquistar: los subarreglos izquierdo y derecho llaman al proceso Dividir de forma recursiva.
Combinar: la clasificación rápida se utiliza como un algoritmo de clasificación local y no requiere ninguna operación de combinación.
Se puede ver que la parte central de la clasificación rápida es el proceso de partición. El siguiente es un ejemplo para explicar en detalle cómo particionar la matriz (imagen tomada de "Introducción a los algoritmos").
Inicialización: seleccione la primitiva P=2, que es el primer elemento de la matriz. i=1,j=i+1=2 (el subíndice de la matriz comienza con 1)
Invariante de bucle: los elementos entre 2 ~ i son todos menores o iguales que P, y los elementos entre i + 1 ~ j son todos mayores o iguales que P.
Proceso de bucle: j va de 2 a n, examina el elemento en la posición j, y si es mayor o igual que P, continúa el bucle. Si es menor que P, intercambie los elementos en la posición j (que no deberían aparecer en el rango i+1~j) con los elementos en la posición i+1 (aún en el rango i+1~j después del intercambio), y al mismo tiempo cambie i+1. Esto mantiene las invariantes de bucle (consulte la descripción de las invariantes de bucle más arriba). Hasta j = n, se completa la última operación de bucle.
Cabe señalar que después de completar el ciclo, el elemento en la posición i debe intercambiarse con el primer elemento de la matriz para cumplir con los requisitos que establecimos primero (correspondiente al i-ésimo paso en la figura).
Los lectores cuidadosos pueden pensar en otro método de partición más sencillo, es decir, sacar las primitivas y almacenarlas en otra matriz del mismo tamaño. Cuando encuentren elementos más pequeños que las primitivas, se almacenarán en la mitad izquierda de la matriz. Los elementos más grandes que los primitivos, se almacenan en la mitad izquierda de la matriz. Los elementos se almacenan en la mitad derecha de la matriz. La complejidad de tales operaciones también es lineal, concretamente Theta(n). Pero la complejidad del espacio se duplica. Esta es también la ventaja de una clasificación rápida in situ.
Copie el código de código de la siguiente manera:
clasificación rápida de clase pública {
QuickSort vacío estático privado (int [] matriz, int inicio, int fin)
{
si(inicio<fin)
{
int key=array[start];//Inicializar y guardar primitivas
int i=start,j;//Inicializar i,j
para(j=inicio+1;j<=fin;j++)
if(array[j]<key)// Si el elemento aquí es menor que el primitivo, intercambie este elemento con el elemento en i+1 y agregue 1 a i. Si es mayor o igual que el primitivo, continúe. el bucle.
{
int temp=matriz[j];
matriz[j]=matriz[i+1];
matriz[i+1]=temp;
yo ++;
}
}
array[start]=array[i];//Intercambiar elementos y primitivas en i
matriz[i]=clave;
QuickSort(array, start, i-1);//llamada recursiva
Ordenación rápida (matriz, i+1, final);
}
}
principal vacío estático público (String [] args)
{
int[] matriz=nuevo int[]{11,213,134,44,77,78,23,43};
QuickSort(matriz, 0, matriz.longitud-1);
para(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+matriz[i]);
}
}
}