Acceso
Iniciar sesión

Galería de mapas mentales algoritmo de clasificación de estructura de datos

algoritmo de clasificación de estructura de datos

Los algoritmos de clasificación a menudo se consideran en estructuras de datos, incluida la clasificación por inserción, la clasificación Hill, la clasificación por burbujas y casi todos los algoritmos de clasificación. La clasificación es el proceso de reorganizar los elementos de la tabla para que los elementos de la tabla satisfagan el orden creciente o decreciente de las palabras clave. .

Editado a las 2023-09-18 01:41:47,

e7qw4qya@bccto.cc

Trabajos recientes Ver más trabajos>>

algoritmo de clasificación de estructura de datos

e7qw4qya@bccto.cc

Trabajos recientes Ver más trabajos>>

Recomendados
Resumen

Datos y estructuras de datos.
- 1
e7qw4qya@bccto.cc
Mapa mental de algoritmo y estructura de datos
e7qw4qya@bccto.cc
Algoritmo de búsqueda de estructura de datos
e7qw4qya@bccto.cc
Estructuras de datos y algoritmos
e7qw4qya@bccto.cc
Implementación de estructura de datos y análisis de algoritmos.
e7qw4qya@bccto.cc
estructura de datos
e7qw4qya@bccto.cc
Estructuras de datos pilas y colas.
e7qw4qya@bccto.cc
Mapa mental de estructura de datos
e7qw4qya@bccto.cc
Estructura de datos - tabla lineal
e7qw4qya@bccto.cc
Estructura de datos 2 (actualización
e7qw4qya@bccto.cc

clasificar

Conceptos básicos de clasificación.

clasificar

Reorganice los elementos de la tabla para que los elementos de la tabla satisfagan el proceso de aumentar o disminuir por palabra clave

estabilidad del algoritmo

Si hay dos elementos Ri y Rj en el algoritmo de clasificación, sus palabras clave correspondientes keyi = keyj, y Ri está delante de Rj antes de ordenar, si después de ordenar, Ri todavía está delante de Rj, este algoritmo es estable. De lo contrario es inestable.

La estabilidad no puede medir la calidad de un algoritmo

tipo de inserción

clasificación por inserción directa

Divida la secuencia en dos partes, ordenada y desordenada, e inserte los bits apropiados en la parte ordenada cada vez.

principio

El estado de la lista a ordenar L [1···n] en un momento determinado durante un determinado proceso de clasificación

1. Encuentre la posición de inserción k de L(i) en L[1···i-1]

2. Mueva todos los elementos en L[k···i-1] hacia atrás una posición

3) Copiar L(i) a L(k)

actuación

Complejidad espacial O (1)

La mejor complejidad temporal es O(n)

Peor complejidad del tiempo O (n ^ 2)

Complejidad de tiempo promedio O (n ^ 2)

Estabilizar

Ser aplicable

lista de secuencia, lista enlazada

clasificación de media inserción

Ordenación por inserción directa mediante búsqueda binaria

Número de comparaciones de elementos

actuación

Complejidad espacial O (1)

mejor complejidad del tiempo

Peor complejidad del tiempo O (n ^ 2)

Complejidad de tiempo promedio O (n ^ 2)

Estabilizar

Ser aplicable

tabla de secuencia

clasificación de colinas

La tabla de clasificación se divide en varias subtablas, cada subtabla se inserta directamente en la clasificación y, finalmente, se realiza toda la clasificación por inserción.

actuación

Complejidad espacial O (1)

Complejidad del tiempo O (n^1.3)

estimar

Peor complejidad del tiempo O (n ^ 2)

inestable

Ser aplicable

tabla de secuencia

tipo de intercambio

Ordenamiento de burbuja

Comenzando desde el principio, compare cada par de elementos adyacentes y muévalos hacia atrás si son más grandes. Después de la comparación, el elemento más grande estará al final. Repite el proceso anterior, no mejor que el más grande, y sigue repitiendo para obtener la secuencia.

actuación

Complejidad espacial O (1)

mejor complejidad del tiempo

Cuando la secuencia está ordenada, el número de comparaciones es n-1, el número de movimientos es 0 y la complejidad del tiempo es O (n).

Peor complejidad del tiempo O (n ^ 2)

Cuando se invierte la secuencia

Complejidad de tiempo promedio O (n ^ 2)

Estabilizar

Ser aplicable

lista de secuencia, lista enlazada

Ordenación rápida

1. Primero, toma un número de la secuencia como número base. 2. Proceso de partición: coloque todos los números mayores que este número a su derecha y todos los números menores o iguales a él a su izquierda. 3. Repita el segundo paso para los intervalos izquierdo y derecho hasta que solo haya un número en cada intervalo.

El peor de los casos es que cada vez que el número del medio seleccionado sea el elemento más grande o más pequeño de la secuencia actual. La clasificación rápida de una tabla de datos de longitud n requiere n divisiones, lo que hace que la complejidad temporal de todo el algoritmo de clasificación sea O (n^2)

actuación

espacio

Peor complejidad espacial O (n)

complejidad espacial promedio

tiempo

mejor complejidad del tiempo

Peor complejidad del tiempo

O(n^2)

complejidad del tiempo promedio

inestable

Ser aplicable

tabla de secuencia

clasificación de selección

Orden de selección simple

Cada vez se selecciona el más pequeño y se intercambia con la posición especificada.

Número de comparaciones n(n-1)/2 Complejidad temporal O(n^2)

actuación

Complejidad espacial O (1)

La mejor complejidad temporal es O(n^2)

Peor complejidad del tiempo O (n ^ 2)

Complejidad de tiempo promedio O (n ^ 2)

inestable

Ser aplicable

lista de secuencia, lista enlazada

clasificación de montón

montón

Una secuencia de n palabras clave L[1 ... n] se denomina montón si y sólo si la secuencia satisface:

pequeño montón de raíces

dagendui

clasificar

Primero construya la columna que se ordenará como un montón y seleccione el elemento más grande (o más pequeño) del montón, que es el elemento superior del montón, y envíelo. Una vez que se genera el elemento superior del montón, el elemento inferior del montón se envía a la parte superior del montón y las propiedades del montón se destruyen. El elemento superior del montón se ajusta hacia abajo para formar un montón nuevamente. el elemento superior del montón se genera repetidamente.

construir una pila

1. Construya un árbol binario en orden secuencial.

{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}

2. Busque ⌊n/2⌋ y ajuste el árbol con él como nodo raíz.

3. Busque el nodo anterior al nodo anterior, continúe ajustando y repita Durante el proceso de ajuste, asegúrese de que el montón ajustado aún cumpla con las reglas.

insertar

Agregue el nodo al último nodo y ajústelo de abajo hacia arriba

borrar

Solo se puede eliminar el nodo raíz

Reemplace el último nodo con el nodo raíz y ajústelo de arriba a abajo.

fusionar ordenar

Clasificación por fusión bidireccional

La tabla a ordenar contiene n registros, que pueden considerarse como n subtablas ordenadas. Cada subtabla tiene una longitud de 1 y luego se ordenan en pares. Obtenga listas ordenadas ⌈n/2⌉ con una longitud de 2 o 1, y luego combínelas en dos pocillos. Repita esto hasta que se fusionen en una lista ordenada de longitud n. Tenga en cuenta la diferencia entre fusión recursiva y fusión no recursiva

actuación

Complejidad espacial O (n)

mejor complejidad del tiempo

Peor complejidad del tiempo

complejidad del tiempo promedio

Estabilizar

Ser aplicable

tabla de secuencia

Ordenación por base

La clasificación por base consiste en ordenar primero por orden inferior y luego por orden superior, y luego por orden superior, y así sucesivamente hasta llegar al orden más alto.