¿Qué es el espacio auxiliar para medicamentos?

Cada pasada de clasificación requiere un espacio auxiliar, y el espacio auxiliar está relacionado con el número de pasadas. ¿El mejor caso es log2? El peor de los casos.

La clasificación rápida fue propuesta por C. A. R. Hoare en 1960.

La idea básica es: dividir los datos que se van a ordenar en dos partes independientes mediante una clasificación, donde todos los datos de una parte son más pequeños que la otra, y luego ordenar rápidamente las dos partes de los datos de acuerdo con Según este método, todo el proceso de clasificación se puede realizar de forma recursiva, de modo que todos los datos se conviertan en una secuencia ordenada.

Datos extendidos

Un algoritmo de clasificación rápida es:

1 Establezca dos variables I y J. Cuando comienza la clasificación, i=0, J = n-. 1;

2. Asigne el primer elemento de la matriz a la clave como datos clave, es decir, clave = a[0]

3. busque de atrás hacia adelante (j-), encuentre el primer valor A [j] que sea menor que la clave e intercambie los valores de A [j] y A [i]

4. Buscar de I hacia atrás, es decir, buscar de adelante hacia atrás (i ++), encontrar la primera clave A [i] mayor que e intercambiar los valores de A [i] y A [j];

5. Repita los pasos 3 y 4, hasta que I = j (en los pasos 3 y 4, no se encuentra ningún valor calificado, es decir, cuando A[j] en 3 no es menor que la clave, y A [i] en 4 no es mayor que la clave, cambie los valores de J e I, de modo que j = j-1, i = i + 1, hasta que se encuentre

Encontrar. el valor que satisface la condición. Durante el intercambio, las posiciones de los punteros I y J permanecen sin cambios. Además, el proceso de i==j debe suceder cuando se completa i+ o j-, lo que finaliza el ciclo). .

Enciclopedia Baidu: clasificación rápida