Inserte el tipo directamente
1 idea de clasificación:
El registro RI a ordenar se inserta en los registros ya ordenados R1, R2, ..., R (N-1).
Para una secuencia aleatoria, comenzando desde el segundo elemento, insertando el elemento en la posición correspondiente en el elemento antes que a su vez. Los elementos antes de que se hayan ordenado.
Primer orden: inserte el segundo elemento en la lista ordenada en el orden anterior (en este momento solo hay un elemento en el anterior, por supuesto que se ordena). Después de eso, se ordenan los dos primeros elementos de esta secuencia.
Segundo ordenar: inserte el tercer elemento en la lista ordenada de la longitud 2 anterior para que se ordenen los dos primeros elementos.
Y así sucesivamente hasta que el enésimo elemento se inserta en la lista ordenada de longitud anterior (N-1).
2 Algoritmo Implementación:
// Insertar directamente la clasificación void straight_insert_sort (int num [], int len) {int i, j, key; para (j = 1; j <len; j ++) {key = num [j]; i = j-1; while (i> = 0 && num [i]> key) {num [i+1] = num [i]; i--; } num [i+1] = Key; }}3 Análisis de rendimiento:
3.1 Complejidad del espacio: como se mencionó anteriormente, se usa una tecla de unidad auxiliar, y la complejidad del espacio es O (1)
3.2 Complejidad del tiempo:
3.2.1 Mejor caso: los registros a ordenar ya están ordenados, luego ordenelos en un viaje, las palabras clave se comparan una vez y los registros se mueven dos veces. Todo el proceso
El número de comparaciones es
El número de movimientos de registros es
Complejidad de tiempo o (n)
3.2.2 Peor Caso: los registros a ordenar ya están en orden inverso, entonces los tiempos de comparación de palabras clave son I (de I-1 a 0), y el registro se mueve (i+2) veces. Todo el proceso
El número de comparaciones es
El número de movimientos de registros es
Complejidad del tiempo o (n^2)
3.2.3 Complejidad de tiempo promedio: O (n^2)
3.3 Estabilidad: estable
Doble la mitad de inserción de inserción
1 idea de clasificación:
Basado en la clasificación directa, los registros que se clasificarán RI se insertan en los registros ya ordenados R1, R2, ..., R (N-1). Dado que los registros R1, R2, ..., R (N-1) se han ordenado, se puede usar "medio encontrar" al buscar la posición de inserción.
2 Algoritmo Implementación:
// Doble la mitad insertar sort void binary_insert_sort (int num [], int len) {int i, j, clave, baja, alta, mitad; para (i = 1; i <len; i ++) {key = num [i]; bajo = 0; alto = i-1; Mid = (bajo+alto)/2; // Encuentra el punto de inserción, el punto de inserción final es bajo, mientras que (bajo <= alto) {if (key <num [mid]) high = Mid-1; más bajo = Mid+1; Mid = (bajo+alto)/2; } // mover registro para (j = i; j> low; j-) {num [j] = num [j-1]; } // Insertar registro num [Low] = Key; }}3 Análisis de rendimiento:
3.1 Complejidad del espacio: como se mencionó anteriormente, se usa una tecla de unidad auxiliar, y la complejidad del espacio es O (1)
3.2 Complejidad del tiempo: aunque la búsqueda de medio fin reduce el número de registros y comparaciones, no reduce el número de movimientos, por lo que la complejidad del tiempo es la misma que el algoritmo de búsqueda directa.
3.2.1 Mejor caso: complejidad de tiempo o (n)
3.2.2 Peor Caso: Complejidad del tiempo o (n^2)
3.2.3 Complejidad de tiempo promedio: O (n^2)
3.3 Estabilidad: estable