¿En qué orden se clasifica la clasificación rápida?

Cada paso de clasificación requiere un espacio auxiliar. El espacio auxiliar está relacionado con el número de pases. El mejor caso es log2?n y el peor caso es n.

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. Todos los datos de una parte son más pequeños que todos los datos de la otra parte y luego ordenarlos de acuerdo con esto. Método Estas dos partes de datos se clasifican rápidamente por separado y todo el proceso de clasificación se puede realizar de forma recursiva, de modo que todos los datos se conviertan en una secuencia ordenada.

Información ampliada

El algoritmo de clasificación rápida de un solo paso es:

1. Establezca dos variables i y j. Cuando comienza la clasificación: i=0. j=N-1;

2. Utilice el primer elemento de la matriz como datos clave y asígnelo a la clave, es decir, key=A[0];

3. de j a Búsqueda hacia adelante, es decir, buscar hacia adelante desde atrás (j--), encontrar el primer valor A [j] que sea menor que la clave e intercambiar los valores de A [j] y A [ i];

4. Busque hacia atrás desde i, es decir, busque de adelante hacia atrás (i), encuentre la primera A [i] mayor que la clave e intercambie los valores de A [i ] y A[j];

5. Repetir los pasos 3 y 4 hasta i=j (En los pasos 3 y 4 no se encuentra ningún valor que cumpla las condiciones, es decir, A[j] en 3 no es menor que la clave, y A [i] en 4 no es mayor que Cuando use la clave, cambie los valores de jey i para que j = j-1 e i = i 1, hasta que se encuentre un valor que cumpla Se encuentran las condiciones al intercambiar, las posiciones de los punteros i y j permanecen sin cambios. Además, el proceso de i == j debe ser exactamente cuando se completa i o j-, y el ciclo finaliza en este momento.

Enciclopedia Baidu: algoritmo de clasificación rápida