Sorteo de inserción directa
La idea de insertar la clasificación directamente es fácil de entender, se ve así:
1. Divida la matriz para que se clasifique en dos partes: ordenadas y sin clasificar. Al principio, se considera que el primer elemento se clasifica.
2. Comience con el segundo elemento, encuentre la posición apropiada del elemento en la subarrray clasificada e insértelo.
3. Repita el proceso anterior hasta que el último elemento se inserta en la subarrray ordenada.
4. La clasificación se completa.
Ejemplo:
La idea es simple, pero el código no es tan fácil de escribir como la clasificación de burbujas. En primer lugar, ¿cómo determinar la posición correcta? Mayor o igual a la izquierda, menor o igual a la derecha? No, se deben considerar muchas condiciones límite, y hay demasiados juicios. En segundo lugar, insertar elementos en una matriz inevitablemente requerirá mover una gran cantidad de elementos. ¿Cómo controlar su movimiento?
De hecho, este no es un problema con el algoritmo en sí, y tiene algo que ver con el lenguaje de programación. A veces, el algoritmo en sí ya es muy maduro, y aún debe cambiarse ligeramente cuando se trata del lenguaje de programación específico. De lo que estamos hablando aquí es el algoritmo Java, así que hablemos de Java.
Para resolver el problema anterior, hemos hecho un pequeño refinamiento del segundo paso. No comenzamos la comparación de la posición inicial de la subarray, sino que comenzamos la comparación inversa de la cola de la subarray. Mientras sea más grande que el número que debe insertarse, avanzamos hacia atrás. Hasta que el número no sea mayor que el número, el número que se insertará se colocará en esta posición vacía. Por lo tanto, podemos escribir el siguiente código:
Insertarray.java
clase pública InsertArray {// Array Private Long [] arr; // el tamaño de los datos válidos en la matriz privada int elems; // Constructor predeterminado public InsertArray () {arr = new Long [50]; } public InsertArray (int max) {arr = new Long [max]; } // Insertar datos public void insert (valor largo) {arr [elems] = valor; Elems ++; } // Mostrar datos public void display () {for (int i = 0; i <elems; i ++) {system.out.print (arr [i]+""); } System.out.println (); } // insertar sort public void insertSort () {long select = 0l; for (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; for (j = i; j> 0 && arr [j - 1]> = select; j--) {arr [j] = arr [j - 1]; } arr [j] = select; }}} Clase de prueba:
TestInserTarray.java
clase pública TestInserTArray {public static void main (String [] args) {InsertArray iarr = new InsertArray (); iarr.insert (85); IARR.INSERT (7856); iarr.insert (12); iarr.insert (8); iarr.insert (5); iarr.insert (56); iarr.display (); iarr.insertsort (); iarr.display (); }} Resultado de impresión:
Rendimiento del algoritmo/complejidad
Ahora discutamos la complejidad del tiempo del algoritmo de inserción directa. Independientemente de la entrada, el algoritmo siempre realiza rondas de clasificación N-1. Sin embargo, dado que el punto de inserción de cada elemento es incierto y muy afectado por los datos de entrada, su complejidad no es segura. Podemos discutir las situaciones mejores, peores y promedio.
1. Mejor caso: a partir de las características del algoritmo, se puede ver que cuando la matriz que se organiza está en orden positivo (la matriz se ordena y el orden es el mismo que el orden requerido, que está en orden ascendente bajo nuestra premisa de discusión). La razón es que en este caso, cada elemento solo debe compararse una vez y no es necesario moverse. La complejidad del tiempo del algoritmo es o (n);
2. Peor caso: obviamente, cuando la matriz a organizar está en orden inverso, es el peor de los casos. En este caso, nuestro número de comparaciones por ronda es la I-1 y el número de tareas es i. El número total de veces es la suma de los primeros n términos de la serie 2n-1, es decir, n^2. La complejidad del tiempo del algoritmo es o (n^2);
3. Situación promedio: del análisis anterior, podemos obtener que el número de operaciones del algoritmo bajo la situación promedio es aproximadamente (n^2)/2 (nota: el cálculo aquí se basa en la asignación y la comparación. Si se basa en el movimiento y la comparación, es aproximadamente n^2/4). Obviamente, la complejidad del tiempo sigue siendo o (n^2).
En cuanto a la complejidad espacial del algoritmo, todos los movimientos se realizan dentro de los datos. La única sobrecarga es que introdujimos una variable temporal (algunas estructuras de datos se denominan "centinelas" en los libros), por lo que su complejidad espacial (espacio adicional) es O (1).
Estabilidad del algoritmo
Dado que solo necesita encontrar una posición que no sea mayor que el número actual y no necesita intercambiar, insertar el tipo directamente es un método de clasificación estable.
Variantes de algoritmo
Si hay muchos datos para organizar, entonces causará muchas sobrecargas cada vez que mires desde atrás a la parte delantera. Para mejorar la velocidad de búsqueda, la búsqueda binaria se puede utilizar para la optimización del rendimiento. Debido a que la eficiencia de la búsqueda binaria es muy alta, se garantiza la complejidad O (N), y la eficiencia de búsqueda puede mejorarse enormemente cuando hay más datos o los datos de entrada tienden a estar en el peor de los casos. En algunos libros, este método se llama plegamiento y medias clasificación de inserción. Su implementación de código es bastante complicada y se puede publicar si tiene tiempo en el futuro.
Además, hay tipos de inserción de 2 vías y tipos de inserción de tabla. El tipo de inserción de 2 vías se mejora aún más sobre la base del plegamiento y la mitad de la inserción, y su número de movimientos se reduce considerablemente, alrededor de N^2/8. Sin embargo, no evita el número de movimientos y no reduce el nivel de complejidad. El tipo de inserción de la tabla cambia completamente la estructura de almacenamiento y no mueve registros, pero se debe mantener una lista vinculada, y el puntero de la lista vinculada se modifica en lugar de mover registros. Por lo tanto, su complejidad sigue siendo o (n^2).
Para el tipo de inserción de 2 vías y el orden de inserción de tabla, puede consultar el libro "Estructura de datos" editado por Yan Weimin y Wu Weimin.
Algoritmo escenarios aplicables
La clasificación de inserción no es aplicable cuando la matriz es grande debido a la complejidad de O (n^2). Sin embargo, cuando hay relativamente pocos datos, es una buena opción, generalmente utilizada como expansión para una clasificación rápida. Por ejemplo, en el algoritmo de clasificación de STL y el algoritmo QSORT de STDLIB, la clasificación de inserción se usa como un suplemento para la clasificación rápida y se usa para clasificar una pequeña cantidad de elementos. Por ejemplo, en la implementación del método de clasificación utilizado en JDK 7 java.util.arrays, cuando la longitud de la matriz a ordenar es inferior a 47, se utilizará la clasificación de inserción.