Estructura de datos, tabla de secuencia, tabla de índice: busque la programación y las ideas básicas de esta pregunta
Hay una secuencia de datos ya ordenada. Se requiere insertar un número en la secuencia de datos ya organizada, pero se requiere que la secuencia de datos aún esté ordenada después de la inserción. Se utiliza el método de clasificación: clasificación por inserción. La operación básica de la clasificación por inserción es insertar un dato en los datos ordenados que se han ordenado, de modo que se obtengan nuevos datos ordenados con el número más uno. una pequeña cantidad de datos. La complejidad temporal de la clasificación es O (n ^ 2). Es un método de clasificación estable. En el mejor de los casos, los datos originales ya están en orden y se agrega un nuevo elemento para mantener la secuencia en orden, o la secuencia se reordena directamente. La complejidad del tiempo en este caso es O (n).
El algoritmo de inserción divide el array a ordenar en dos partes: la primera parte contiene todos los elementos del array, excepto el último elemento (dejando el array con un espacio más para permitir la inserción), y la segunda parte La parte solo contiene este elemento (el elemento que se insertará). Una vez ordenada la primera parte, este último elemento se inserta en la primera parte ordenada.
La idea básica de la ordenación por inserción es: en cada paso, un registro a ordenar se inserta en la posición apropiada del archivo previamente ordenado según el tamaño de su valor clave, hasta que todos estén insertados. .
Clasificación por inserción directa
La clasificación por inserción directa es un método de clasificación por inserción simple. Su idea básica es insertar los registros que se ordenarán uno por uno según el tamaño de sus valores clave. En la secuencia ordenada ya ordenada, hasta que se inserten todos los registros, se obtiene una nueva secuencia ordenada. [1]
Por ejemplo, se sabe que el conjunto de registros a ordenar es:
60, 71, 49, 11, 24, 3, 66
Supongamos que durante el proceso de clasificación, los primeros tres registros se han reorganizado en orden de valor clave creciente para formar una secuencia ordenada:
49, 60, 71
Los registros a ordenar son El cuarto registro (es decir, 11) se inserta en la secuencia ordenada anterior para obtener una nueva secuencia ordenada que contiene 4 registros. Primero, debes encontrar la posición de inserción de 11 y luego insertarla. Puede colocar 11 en la primera unidad r [0] de la matriz. Esta unidad se llama puesto de vigilancia y luego buscar de derecha a izquierda comenzando desde 71. 11 es menor que 71. Mueva 71 una posición hacia la derecha. 11 es menor que 60 y mueve 60 una posición hacia la derecha, 11 es menor que 49 y mueve 49 una posición hacia la derecha. En este momento, compare el valor de 11 con r [0], 11≥r [0. ], y su posición de inserción es r[1] . Supongamos que 11 es mayor que el primer valor r[1]. Su posición de inserción debe estar entre r[1] y r[2]. Dado que 60 se ha desplazado hacia la derecha, la posición restante queda exactamente para 11. Los siguientes registros se insertan en la secuencia ordenada uno por uno de la misma manera. . Si el número de registros es n, se realizarán n-1 operaciones de clasificación consecutivas para completarlo.
La idea del algoritmo de clasificación por inserción directa:
(1) Configure el centinela de monitoreo r[0] y asigne el valor del registro que se insertará a r[0 ];
(2) Establecer la posición inicial j;
(3) Buscar en la matriz y mover el registro j hacia atrás durante la búsqueda hasta r[0].key≥ r[j] .key;
(4) Inserte r[0] en la posición de r[j 1].
Algoritmo de clasificación por inserción directa:
public void zjinsert (Redtype r[], int n)
{
int I, j ;
Escriba nuevamente temp;
for (i=1;ilt;n;i)
{
temp = r[i ];
j=i-1;
mientras (jgt;-1 amp; amp; temp.keylt; r[j].key)
{
r[j 1]=r[j];
j--;
}
r[j 1] =temp;
}
}