Quicksort es un algoritmo de clasificación más utilizado y más eficiente, y a menudo se menciona durante el proceso de entrevista. Expliquemos sus principios en detalle y damos una implementación de la versión Java.
Idea de clasificación rápida:
Dos partes independientes se dividen clasificando el elemento de datos establecido RN en un viaje. Una parte de la palabra clave es más pequeña que la otra parte. Luego ordene las palabras clave de las dos partes una por una hasta que solo haya un elemento independiente, y toda la colección de elementos está en orden.
El proceso de clasificación rápida: el método de cavar agujeros y números de llenado (este es un nombre muy vívido), para un elemento establecido R [bajo ... alto], primero tome un número (generalmente R [bajo]) como referencia y R [bajo] reorganizan todos los elementos como el punto de referencia.
Todos los más pequeños que R [bajo] se colocan en el frente, todos los más grandes que R [bajo] se colocan en la parte posterior, y luego R [bajo] se usa como límite, y R [bajo ... alto] es dividido en dos subconjuntos y luego dividido. Hasta bajo> = alto.
Por ejemplo: el proceso de realizar una clasificación rápida de r = {37, 40, 38, 42, 461, 5, 7, 9, 12} es la siguiente (Nota: La siguiente tabla de elementos descritos a continuación comienza desde 0)::
| Secuencia original | 37 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 12 |
| 1: alto-> bajo | 12 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 12 |
| 1: bajo -> alto | 12 | 40 | 38 | 42 | 461 | 5 | 7 | 9 | 40 |
| Dos: alto-> bajo | 12 | 9 | 38 | 42 | 461 | 5 | 7 | 9 | 40 |
| Dos: bajo -> alto | 12 | 9 | 38 | 42 | 461 | 5 | 7 | 38 | 40 |
| Tres: alto -> bajo | 12 | 9 | 7 | 42 | 461 | 5 | 7 | 38 | 40 |
| Tres: bajo -> alto | 12 | 9 | 7 | 42 | 461 | 5 | 42 | 38 | 40 |
| Cuatro: alto -> bajo | 12 | 9 | 7 | 5 | 461 | 5 | 42 | 38 | 40 |
| Cuatro: bajo -> alto | 12 | 9 | 7 | 5 | 461 | 461 | 42 | 38 | 40 |
| Resultados de clasificación única | 12 | 9 | 7 | 5 | 37 | 461 | 42 | 38 | 40 |
Comience a seleccionar la base base = 37, la tabla de abajo es baja = 0, alta = 8, comenzando desde alto = 8, si r [8] <base, escriba el contenido en la posición alta en r [bajo] y luego alto La posición está vacía, baja = baja +1;
Comience a sondear desde Low, ya que bajo = 1, R [bajo]> base, escriba r [bajo] a R [alto], alto = alto -1;
Se detecta bajo <High, por lo que la primera clasificación rápida aún debe continuar:
En este momento bajo = 1, alto = 7, porque r [alto] <base, r [alto] se escribe en r [bajo], bajo = bajo + + 1;
La detección de inicio de la base baja, baja = 2, R [baja]>, por lo que R [bajo] se escribe en R [alto], alto = alto-1;
Continuar detectando bajo es menos que alto
En este momento bajo = 2, alto = 6, de manera similar, r [alta] <base, escriba r [alto] a r [bajo], bajo = bajo++1;
Continúe detectando de bajo, bajo = 3, alto = 6, R [bajo]> base, escriba R [bajo] a R [alto], alto = alto-1;
Continuar detectando que el bajo es menos que alto
En este momento bajo = 3, alto = 5, de manera similar, r [alta] <base, escriba r [alto] en r [bajo], bajo = bajo +1;
Continúe sondeando de bajo, bajo = 4, alto = 5, porque r [bajo]> base, escriba r [bajo] en R [alto], alto = alto -1;
En este momento, se detecta bajo == High == 4;
Luego haga una clasificación rápida de subsecuencias rs1 = {12,9,7,5} y rs2 = {461,42,38,40} hasta que solo haya un elemento en RSI, o ningún elemento.
(Nota: en el formulario anterior, puede ver que hay algunos datos duplicados en la clasificación (sin datos duplicados en los datos originales). Esto se debe a que los datos en esa ubicación no están borrosos. Observamos los datos de la memoria Bloquear en un momento específico.
Implementación de Java de clasificación rápida:
La copia del código es la siguiente:
Private estático booleano isEtimty (int [] n) {
return n == null || n.length == 0;
}
// //////////////////////////////////////////// //
/**
* Idea de algoritmo de clasificación rápida: método para cavar agujeros y llenado:
*
* @param n array para ser ordenado
*/
public static void Quicksort (int [] n) {
if (isEmpty (n))
devolver;
Quicksort (N, 0, N.Length - 1);
}
Public static void Quicksort (int [] n, int l, int h) {
if (isEmpty (n))
devolver;
if (l <h) {
int pivot = particion (n, l, h);
Quicksort (N, L, Pivot - 1);
Quicksort (n, pivote + 1, h);
}
}
privado static int partition (int [] n, int intar, int end) {
int tmp = n [inicio];
while (inicio <end) {
while (n [end]> = tmp && start <end)
fin--;
if (inicio <end) {
n [inicio ++] = n [end];
}
while (n [inicio] <tmp && start <end)
inicio ++;
if (inicio <end) {
n [final--] = n [inicio];
}
}
n [inicio] = tmp;
inicio de regreso;
}
Hay una función como esta en el código:
La copia del código es la siguiente:
Public static void Quicksortswap (int [] n, int l, int h)
Esta función se puede implementar para clasificar los elementos de datos en el elemento establecido entre posiciones específicas de L y H.
Eso es todo para una clasificación rápida.