Se refiere a una clasificación en la que todos los elementos se almacenan en la memoria durante la clasificación.

Se refiere a un proceso de clasificación en el que todos los elementos no se pueden almacenar en la memoria al mismo tiempo durante la clasificación, y se mueven constantemente entre la memoria interna y externa durante el proceso de clasificación.

De L [2] ~ L [n-1], cada vez que el elemento a ordenar L [i] se inserta en la secuencia ordenada previamente, y los elementos más grandes que L [i] se mueven hacia atrás en orden (compare los bordes adelante, mueva el elemento hacia atrás)

Lo mejor: los elementos de la tabla ya están ordenados

Lo peor: orden inverso

promedio

Estabilizar

Tablas lineales adecuadas para almacenamiento secuencial y almacenamiento vinculado; cuando se trata de almacenamiento vinculado, la posición del elemento especificado se puede buscar de adelante hacia atrás (de hecho, la mayoría de los algoritmos de clasificación internos solo son adecuados para el almacenamiento secuencial)

Primero doble por la mitad para encontrar la posición donde se insertará el elemento y luego mueva todos los elementos después del elemento que se insertará de manera uniforme.

Número de comparaciones: (independientemente del estado inicial de la tabla)

Número de movimientos: depende del estado inicial de la tabla ordenada.

Estabilizar

Se aplica solo a tablas de secuencia

Organice los elementos con un intervalo de d1 (paso/incremento) en un grupo, divida la tabla de clasificación en varias subtablas, realice una clasificación por inserción directa dentro de cada subtabla, luego reduzca el incremento d2 y repita el proceso anterior hasta di =1 hasta

inestable

Solo es aplicable cuando la tabla lineal se almacena secuencialmente (porque se utilizan las características de acceso aleatorio del almacenamiento secuencial)

Compara los valores de los elementos adyacentes de atrás hacia adelante (o de adelante hacia atrás) si están en orden inverso, intercámbialos hasta comparar la secuencia. El resultado de cada ronda será intercambiar el elemento más pequeño al primero. posición de la secuencia a ordenar (o al elemento más grande Los elementos se intercambian al final de la columna a ordenar), y este ciclo se puede realizar n-1 veces.

Mejor (no se produce ningún intercambio en el primer pase de clasificación, salte directamente del bucle)

Peor (en orden inverso)

Estabilizar

La subsecuencia generada en la clasificación de burbujas debe estar ordenada globalmente (a diferencia de la inserción directa), y todos los elementos que contiene deben ser mayores o menores que todos los elementos de la subsecuencia desordenada, y cada pasada de clasificación colocará un elemento en su posición final.

Según el método de dividir y conquistar, cada vez que se toma un determinado elemento pivote como punto de referencia, la secuencia se divide en dos subtablas, la izquierda y la derecha, y luego se ordena de forma recursiva dentro de las subtablas.

Peor (ordenado o invertido)

Mejor (simétrico, es decir, la secuencia se divide equitativamente para cada punto de referencia)

inestable

El algoritmo con mejor rendimiento promedio entre los algoritmos de clasificación interna

No se genera ninguna subsecuencia ordenada durante el proceso, pero cada operación de clasificación colocará el elemento pivote (base) en su posición final.

①Para la clasificación por fusión de k vías, se deben asignar k búferes de entrada y 1 búfer de salida en la memoria

② Ordene internamente un total de N registros (usando un algoritmo de clasificación interno) y genere r segmentos de fusión iniciales ordenados internamente (r = 『N/L], L es el número de buffers de entrada en la memoria)

③Fusionando S viajes y k rutas,

Es hora de leer y escribir en la memoria externa.

Tiempo necesario para la clasificación interna

Tiempo de fusión interna

1) Aumente el número de rutas de fusión k, y solo necesita una fusión equilibrada de múltiples vías

2) Reducir el número de segmentos de fusión iniciales r

Para evitar que la fusión interna se vea afectada por el aumento de k, se introduce un árbol perdedor. Los k nodos de hoja almacenan respectivamente los registros de los k segmentos de fusión que actualmente participan en la comparación durante el proceso de fusión. Memorice las "fallas" en los subárboles izquierdo y derecho ", el nodo raíz apunta al número mínimo;

El número inicial de comparaciones es k-1. Después de eso, solo se necesitan "log2k] tiempos de comparación para seleccionar un valor mínimo.

Después de introducir el árbol perdedor, el número de comparaciones no tiene nada que ver con k; pero a medida que k aumenta, el número de búferes de entrada puede aumentar. Si el espacio total de memoria permanece sin cambios, es necesario reducir la capacidad de cada búfer. reducir el número de intercambios de memoria interna y externa.

Aumente la longitud de cada segmento de combinación (pero no la longitud fija), reduciendo así la cantidad de segmentos de combinación

Deje que el archivo inicial a ordenar sea FI, el archivo de salida del segmento de fusión inicial sea FO y el área de trabajo de la memoria sea WA (puede acomodar registros w)

1) Ingrese w registros de FI al espacio de trabajo WA.

2) Seleccione el registro con el valor mínimo de palabra clave de WA y regístrelo como registro MINIMAX.

3) Salida de registros MINIMAX a FO.

4) Si FI no está vacío, ingrese el siguiente registro de FI en WA.

5) Seleccione el registro de palabra clave más pequeño de todos los registros en WA con palabras clave mayores que el registro MINIMAX como nuevo registro MINIMAX.

6) Repita 3)~5) hasta que no se pueda seleccionar ningún nuevo registro MINIMAX en WA, obteniendo así un segmento de fusión inicial y enviando una bandera de fin del segmento de fusión a FO.

7) Repita 2)~6) hasta que WA esté vacío. A partir de esto, se obtienen todos los segmentos fusionados iniciales.

1) Cada segmento de fusión inicial corresponde a un nodo hoja, y el número de bloques contenidos en el segmento de fusión es el peso de la hoja.

2) Combinar árbol WPL = la suma de las longitudes de ruta ponderadas de todos los nodos de hoja en el árbol

3) El número de E/S de disco durante el proceso de fusión = WPL del árbol fusionado*2

1) Complementar el párrafo virtual

2) Construir un árbol k-ary Huffman

1) La clasificación rápida se considera el mejor método entre los métodos de clasificación interna basados ​​en comparaciones actuales. Cuando las palabras clave que se van a clasificar se distribuyen aleatoriamente, el tiempo promedio de clasificación rápida es el más corto.

2) La clasificación en montón requiere menos espacio auxiliar que la clasificación rápida y no sufre el peor de los casos que pueda tener la clasificación rápida: ambas clasificaciones son inestables.

3) Si se requiere que la clasificación sea estable y la complejidad del tiempo es O (nlog2n), se puede utilizar la clasificación por fusión.

La ordenación por fusión bidireccional trata la lista que se va a ordenar como n sublistas (cada sublista tiene una longitud de 1) y luego las fusiona de forma recursiva hasta que se sintetiza una lista ordenada de longitud n.

eficiencia espacial

eficiencia de tiempo

Estabilizar

Utilice la idea de clasificación de varias palabras clave para tratar con palabras clave lógicas únicas

Bit más significativo primero (MSD)

Menos significativo primero (LSD)

La base r = 10 requiere 10 colas en cadena; cada palabra clave tiene 3 bits y requiere tres operaciones de "asignación" y "recopilación".

eficiencia espacial

eficiencia de tiempo

Estabilizar

La clasificación i-ésima selecciona el elemento con la palabra clave más pequeña de L [i... n] y lo intercambia con L [i]. Cada pasada puede determinar la posición final de un elemento.

Número de comparaciones: n(n-1)/2

Número de movimientos

inestable

montón

Algoritmo de clasificación

① Para obtener un árbol binario completo con n nodos, comience a filtrar desde el nodo principal del último nodo ("n/2]) e intercambie los nodos principal e secundario para que se llame un montón raíz grande (el nodo principal puede continuar bajar hasta el final) y luego filtrar los subárboles enraizados en cada nodo ("n/2]~1)

②Después de generar el elemento superior del montón, intercambie el último elemento superior del montón con el elemento superior del montón, y luego intercambie recursivamente el orden del elemento superior del montón con el mayor de los hijos.

Algoritmo de creación de montón raíz grande

Algoritmo de clasificación de montón

Primero coloque el nuevo nodo al final del montón, luego apúntelo hacia arriba para la operación de ajuste.

complejidad del tiempo

eficiencia espacial

eficiencia de tiempo

inestable

Adecuado para almacenamiento secuencial (debido al acceso aleatorio)