La clasificación rápida es encontrar un elemento (originalmente puede encontrar uno) como referencia (pivote), y luego dividir la matriz para que el valor del elemento a la izquierda de la referencia no sea mayor que el valor de referencia, y el valor del elemento a la derecha de la referencia no es menor que el valor de referencia. Ordena recursivamente rápida, ajuste los otros elementos N-1 a la posición correcta después de la clasificación. Finalmente, cada elemento está en la posición correcta después de la clasificación y la clasificación se completa. Por lo tanto, el algoritmo central del algoritmo de clasificación rápida es la operación de partición, es decir, cómo ajustar la posición del punto de referencia y ajustar la posición final del punto de referencia de retorno para dividir y conquistar la recursión.
El algoritmo para una clasificación rápida es:
1) Establezca dos variables I y J, cuando la clasificación comienza: i = 0, j = n-1;
2) Use el primer elemento de matriz como datos de clave y asignarlos a la clave, es decir, clave = a [0];
3) Comience desde J para buscar hacia adelante, es decir, comience desde atrás para buscar hacia adelante (J--), encuentre el primer valor A [J] más pequeño que la clave, y cambie una [j] y a [i];
4) Comience desde i para buscar hacia atrás, es decir, comenzar de adelante hacia atrás (i ++), encuentre el primero a [i] más grande que la llave e intercambie un [i] y a [j];
5) Repita los pasos 3 y 4 hasta que i = J; 4 no es mayor que el cambio clave los valores de J e I para que J = J-1, i = i+1 hasta que se encuentre el valor que cumple con las condiciones y al intercambiar, la posición del puntero J permanece sin cambios.
Déjame darte un ejemplo, esto puede no ser fácil de entender. Suponga que la secuencia a ordenar es
La copia del código es la siguiente:
paquete com.zc.ManyThread;
import java.util.random;
/**
* Clasificación rápida
* @Author Administrator
*
*/
clase pública QSORT {
int [] fecha;
Public Qsort (int [] fecha) {
this.Date = date;
}
/**
* Función de intercambio
* @param a
* @param yo
* @param j
*/
swap vacío privado (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/****************************
* Ordenar función
* @param a
* @param lo0
* @param hola0
* @devolver
*/
int [] Quicksort (int a [], int lo0, int hi0) {// El método de división y tratamiento es dividir la matriz en un [lO0..Q-1] y un [q+1..hi0]
int lo = lo0;
int hi = hi0;
int Mid;
if (hi0> lo0) {
Mid = a [(Hi0+lo0)/2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <medio)) ++ lo;
while ((hi> lo0) && (a [hi]> mid)) --hi;
if (lo <= hi) {
intercambio (a, lo, hola);
++ lo;
--Hola;
}
}
if (lo0 <hi) {
Quicksort (a, lo0, hola);
}
if (lo <hi0) {
Quicksort (A, LO, Hi0);
}
}
regresar a;
}
/********************
*
* Crear datos de matriz duplicados
**********************/
privado static int [] creatate (int count) {
int [] data = new int [count];
para (int i = 0; i <data.length; i ++) {
datos [i] = (int) (math.random ()*count);
}
devolver datos;
}
/**
* No hay datos de matriz duplicados
* @param cuenta
* @devolver
*/
privado static int [] creatate1 (int count) {
int [] data = new int [count];
Rand aleatorio = new Random ();
booleano [] bool = nuevo booleano [100];
int num = 0;
para (int i = 0; i <count; i ++) {
hacer {
// Si el número generado es el mismo, continúa en bucle
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
datos [i] = num;
}
devolver datos;
}
/************** Función principal **********************/
public static void main (string [] args) {
Final int count = 10;
int [] data = creatate1 (count);
para (int n: data) {
System.out.print (n+"/t");
}
QSORT data1 = nuevo QSort (datos);
System.out.println ();
int [] a = data1.quicksort (datos, 0, count-1);
para (int n: a) {
System.out.print (n+"/t");
}
}
}
Los resultados son los siguientes:
Lo anterior es todo el contenido descrito en este artículo.