Complejidad del tiempo
Promedio: O (NLGN)
El peor de los casos: o (n*n), ocurre cuando los datos ya están en el estado de clasificación.
1. Seleccione un valor a [i] de los datos como referencia
2. Tomando una [i] como referencia, divida los datos en 2 partes: P1 y P2. Todos los datos en p1≤a [i], todos los datos en p2> a [i], y los datos se convierten en {{p1} {a [i]} {p2}}
3. Repita los pasos anteriores con P1 y P2 hasta que solo queden 1 datos en cada parte.
4. Los datos se clasifican en orden ascendente
Ejemplo básico:
Datos sin procesar:
{3, 9, 8, 5, 2, 1, 6} Paso 1: seleccione los primeros datos: 3
Paso 2: Divida los datos en 2 partes, el lado izquierdo es ≤3 y el lado derecho es mayor que> 3:
{2,1} {3} {9,8,5,6} Paso 3: Repita los pasos anteriores para cada parte hasta que solo queden 1 datos en cada parte:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8}}} Paso 4: Los datos se ordenan en orden ascendente:
{1} {2} {3} {5} {6} {8} {9}Los datos en el programa generalmente se almacenan en una matriz. Tomando una matriz de tipo int como ejemplo, puede escribir los pasos anteriores en un prototipo de función QuickSort:
Quicksort (int begin, int end) {// Begin es el valor de índice de los primeros datos de la matriz, end es el valor de índice de los últimos datos de la matriz +1 // Si solo hay 1 datos o 0 datos, el programa regresa si (begin == end || begin == (end-1)) return; int p = en [begin]; // p es los datos de referencia seleccionados, seleccione los primeros datos int a = begin +1; // a como el valor de índice de la línea de división de datos de 2 partes int b = a; // b es el valor de índice de los datos que se compararán para (; b <end; b ++) {// Compare los datos en la matriz con los datos de referencia en secuencia if (en [b] <p) {// si los datos <datos de referencia, muévalo a la izquierda si (a == b) {a ++; continuar;} // Si los datos ya están a la izquierda, no moverá int temp = en [a]; // mover los datos a la izquierda en [a] = en [b]; en [b] = temp; a ++; // Mueve la línea divisoria a la derecha}} en [begin] = en [a-1]; // whik el valor de referencia a la mitad de 2 conjuntos de datos en [a-1] = p; if (a-1> begin) {// Si hay datos a la izquierda, repita los pasos anteriores QuickSort (comenzar, a); } if (end-1> a) {// Si hay datos a la derecha, repita los pasos anteriores QuickSort (a, end); } devolver; // Si no hay datos} Optimización de algoritmo
Se puede decir que el algoritmo de clasificación rápida anterior es el tipo rápido más básico porque no tiene en cuenta ningún datos de entrada. Sin embargo, es fácil encontrar los defectos de este algoritmo: es cuando nuestros datos de entrada están básicamente ordenados o incluso completamente ordenados, el algoritmo degenera en la clasificación de burbujas, ya no o (nn), sino o (n^2).
La causa raíz es que en nuestra implementación de código, solo comenzamos desde la primera matriz a la vez. Si usamos el "Leader de tres", es decir, los valores medios de ARR [Low], ARR [alto], ARR [(bajo+alto)/2] Como el registro de pivote, el rendimiento de la clasificación rápida en el peor de los casos se puede mejorar enormemente. Sin embargo, todavía no podemos mejorar su rendimiento a O (N) en el caso ordenado por la matriz. También hay formas de mejorar el rendimiento del tiempo de la clasificación rápida en el peor de los casos a diversos grados.
Además, la clasificación rápida requiere una pila recursiva, que generalmente no es muy profunda y está en el nivel log (N). Sin embargo, si la longitud de las dos matrices divididas a la vez está severamente desequilibrada, en el peor de los casos, la profundidad de la pila aumentará a O (N). En este momento, la complejidad espacial traída por el espacio de la pila no puede ser ignorada. Si se agrega la sobrecarga de variables adicionales, incluso puede alcanzar una aterradora complejidad del espacio O (n^2) aquí. Por lo tanto, la peor complejidad espacial de la clasificación rápida no es un valor fijo, y puede que ni siquiera esté al mismo nivel.
Para resolver este problema, podemos comparar las longitudes de los extremos después de cada división y ordenar las secuencias cortas primero (el propósito es finalizar estas pilas primero para liberar el espacio), lo que puede reducir la profundidad máxima de regreso al nivel O (N).
Aquí hay tres ideas de optimización para una clasificación rápida:
Para matrices pequeñas, la clasificación de inserción se puede usar para evitar llamadas recursivas. Por ejemplo, cuando (hi <= lo + m), puede ir a insertar el tipo.
Use la mediana de una subarría para cortar la matriz. Esto da como resultado un mejor corte, pero a costa de calcular la mediana.
Si la matriz contiene una gran cantidad de elementos repetidos, se puede utilizar un corte a tres vías. Divida la matriz en tres partes, correspondientes a elementos de matriz más pequeños que, igual y mayores que los elementos de corte respectivamente. La implementación del código es la siguiente:
privado static void sort1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt--); } else {i ++; } sort (a, lo, lt - 1); ordenar (a, gt + 1, hola); }}