¿Cuánto espacio auxiliar requieren los distintos algoritmos de clasificación?

1. La complejidad espacial de todos los métodos de clasificación simples (incluida la inserción directa, la burbuja y la selección simple) y la clasificación del montón es O (1);

2. La clasificación rápida es O (logn), que es el auxiliar. el espacio requerido por la pila;

3. La clasificación por fusión requiere la mayor cantidad de espacio auxiliar y su complejidad espacial es O (n)

4; Puntero de cola, por lo que la complejidad del espacio es O (rd).

No sé qué responder, hay demasiadas categorías. Aquí te dejamos algunos sencillos, ¡espero que te ayuden!

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 de comparaciones es al menos n-1; el número máximo es (n-1)(n 2)/2

El número mínimo de los movimientos son 0; el número máximo es (n- 1)(n 4)/2

Utilice espacio de almacenamiento auxiliar, que es un tipo estable;

2. Ordenación por inserción plegable: el número de comparación mínimo es el mismo que el número máximo, que es 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: el menor número de comparaciones es: n-1 veces, y la que tiene mayor complejidad temporal se expresa como o (N2);

El número mínimo de movimientos es 0 y el número máximo es La complejidad del tiempo se expresa como O (n2).

Usando espacio de almacenamiento secundario, esta es una clasificación estable;

4. Clasificación de selección simple: no hay mucha diferencia en el número de comparaciones, 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 los movimientos se expresan como O (N2);

El espacio de almacenamiento auxiliar utilizado es al menos log2n y como máximo n cuadrados;

6. de comparaciones y movimientos No hay diferencia, ambos son O (n * log2n);

El uso de espacio de almacenamiento auxiliar es una clasificación inestable;

7. número de comparaciones y movimientos La diferencia es O (n * log2n);

Requiere n espacio de almacenamiento auxiliar, que es una clasificación estable;