Compare varios algoritmos de clasificación con los mejores y peores escenarios.
Por ejemplo, al ordenar N elementos de almacenamiento secuencial, a[0] actúa como un "centinela" (es decir, a[0] no almacena datos, sino que sirve como espacio de almacenamiento auxiliar).
1 Clasificación por inserción directa: el número mínimo de comparaciones es n-1; el número máximo es (n-1)(n 2)/2
El número mínimo de movimientos es 0; el número máximo es (n-1 )(n 4)/2
Utilizando espacio de almacenamiento auxiliar, esta es una clasificación estable;
Clasificación por inserción doble: el mínimo El número de comparación y el número máximo son iguales, ambos son n*log2n (2 es la base y la base significa lo mismo).
El número mínimo de movimientos es 0 y la complejidad de tiempo máxima es O (N2 (el cuadrado de n, también expresado a continuación);
Usando espacio de almacenamiento auxiliar, esto; es una clasificación estable;
3 Clasificación de burbujas: la comparación mínima es: n-1 veces, y la complejidad temporal máxima se expresa como o(N2);
El número mínimo de los movimientos son 0 y la complejidad temporal máxima se expresa como O (n2).
Utilizando espacio de almacenamiento secundario, esta es una clasificación estable;
4 Clasificación de selección simple: el número de comparaciones no es muy diferente, todas son n (n-1)/ 2 ;
El número mínimo de movimientos es 0 y el número máximo de movimientos es 3 (n-1);
Utilizando espacio de almacenamiento secundario, esta es una clasificación estable;
5. Clasificación rápida: la complejidad temporal mínima del número de comparaciones y movimientos se expresa como O(n * log2n);
La complejidad temporal del número máximo de comparaciones y movimientos es expresado como O(N2);
El espacio de almacenamiento auxiliar utilizado es al menos log2n y como máximo n al cuadrado; es una clasificación inestable;
6 Clasificación de montón: no hay diferencia; en el número de comparaciones y movimientos, ambos O (n * log2n);
El uso del espacio de almacenamiento auxiliar es una clasificación inestable;
7 Clasificación por combinación bidireccional: no hay diferencia en el número de comparaciones y movimientos, ambos son O (n * log2n);
Requiere n espacio de almacenamiento auxiliar, que es una clasificación estable;
Además, hay muchas clasificaciones métodos, como clasificación Hill, clasificación por base, clasificación por 2 inserciones, etc. No los enumeraré todos aquí. ¡Espero que esto ayude! !