Un algoritmo es un conjunto de reglas bien definidas que se utilizan para resolver un problema en un número limitado de pasos. En pocas palabras, es el proceso de resolución de problemas por computadora. En este proceso, ya sea que esté formando una idea para resolver un problema o escribiendo un programa, está implementando un determinado algoritmo. El primero es un algoritmo implementado mediante razonamiento y el segundo es un algoritmo implementado mediante operación.
Un algoritmo debe tener las siguientes cinco características importantes:
1. Finitud: un algoritmo debe garantizar que finaliza después de ejecutar un número finito de pasos;
2. Exactitud: Cada paso del algoritmo debe estar claramente definido;
3. Entrada: un algoritmo tiene 0 o más entradas para describir la situación inicial del operando;
4. Salida: un algoritmo tiene una o más salidas para reflejar los resultados del procesamiento de los datos de entrada. Un algoritmo sin resultado no tiene sentido;
5. Viabilidad: en principio, el algoritmo puede ejecutarse con precisión y puede ser completado por personas que utilicen lápiz y papel para realizar un número limitado de operaciones.
La clasificación por combinación (MERGE SORT) es otro tipo de método de clasificación diferente. El significado de la combinación es fusionar dos o más secuencias de datos ordenadas en una nueva secuencia de datos ordenada, por lo que también se denomina algoritmo de combinación. Su idea básica es suponer que la matriz A tiene N elementos, entonces se puede considerar que la matriz A consta de N subsecuencias ordenadas, cada subsecuencia tiene una longitud de 1 y luego se fusiona de dos en dos para obtener N/2 Una subsecuencia ordenada de Luego, la longitud 2 o 1 se fusiona de dos en dos, y esto se repite hasta que se obtiene una secuencia de datos ordenada de longitud N. Este método de clasificación se denomina clasificación de fusión bidireccional.
Por ejemplo, la matriz A tiene 7 datos, que son: 49 38 65 97 76 13 27. Luego, el proceso de operación de usar el algoritmo de clasificación por combinación se muestra en la Figura 7:
Valor inicial[49][38][65][97][76][13][27]
Visto como compuesto de 7 subsecuencias de longitud 1. Después de la primera fusión [38 49] [65 97] [13 76] [27]
Visto como compuesto por 4 subsecuencias de longitud 1 o 2. Después de la segunda fusión [38 49 65 97] [13 27 76]
Visto como compuesto por 2 subsecuencias de longitud 4 o 3. Después de la tercera fusión [13 27 38 49 65 76 97]
Figura 6 Diagrama de proceso del algoritmo de clasificación de fusión La operación principal del algoritmo de fusión es fusionar dos secuencias ordenadas adyacentes en una matriz unidimensional en una secuencia ordenada. El algoritmo de fusión también se puede implementar utilizando un algoritmo recursivo, que tiene una forma relativamente simple, pero tiene poca practicidad.
El número de fusiones en el algoritmo de fusión es una cantidad muy importante. Según los cálculos, cuando hay de 3 a 4 elementos en la matriz, el número de fusiones es 2, cuando hay de 5 a 8 elementos, el número de fusiones es 3. , Y cuando hay de 9 a 16 elementos, el número de fusiones es 4. Según esta regla, cuando hay N subsecuencias, se puede inferir que el número de fusiones es
X (2>=N, la X más pequeña que cumple la subcondición).
Descripción del algoritmo de burbuja:
Antes de explicar el algoritmo de clasificación de burbujas, primero introduzcamos un algoritmo que coloca el número más grande entre 10 números (en la matriz A) en la última posición. El algoritmo se describe a continuación:
(1) De la matriz A [1] a A [10], compare dos números adyacentes en pares. Es decir, se compara A[1] con A[2], y después de la comparación, se compara A[2] con A[3],... y finalmente se compara A[9] con A[10].
(2) Durante cada comparación, si el número anterior es mayor que el último, los dos números se intercambiarán, es decir, el número mayor se moverá hacia atrás y el número menor se moverá hacia adelante. Por ejemplo, en la primera comparación, si A[1] es mayor que A[2], los valores de A[1] y A[2] se intercambian. La siguiente figura utiliza 6 datos para ilustrar el algoritmo anterior.
Supongamos que los 6 datos son: A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 La primera vez, se comparan A[1]=5 y A[2]=7, 7>5, no se realiza ningún intercambio.
5 7 4 3 8 6 La segunda vez, se comparan A[2]=7 y A[3]=4, 4<7, intercambian.
Entonces los datos después de la segunda comparación son 5 4 7 3 8 6
5 4 7 3 8 6 La tercera vez, se comparan A[3]=7 y A[4]=3, 3<7, intercambian.
Entonces los datos después de la tercera comparación son 5 4 3 7 8 6
5 4 3 7 8 6 La cuarta vez, se comparan A[4]=7 y A[5]=8, 8>7, no se realiza ningún intercambio.
5 4 3 7 8 6 La quinta vez, se comparan A[6]=6 y A[5]=8, 6<8, intercambian.
Entonces el quinto y último resultado es
5 4 3 7 6 8
************************************************** * *****
Descripción del algoritmo de clasificación por selección:
Antes de presentar el método de clasificación por selección, introduzcamos un algoritmo que coloca el número más pequeño en la primera posición. Por supuesto, también puede utilizar el método de clasificación por burbujas mencionado anteriormente. Ahora usamos un nuevo algoritmo: su ideología rectora. Date prisa para cambiar de posición al principio, pero empieza con A [1] comienza a verificar uno por uno. Para ver qué número es el más pequeño, escriba la posición P del número. Una vez completado el escaneo, intercambie A [P] y A [1]. [1] a A[ 10] se mueve a la posición delantera. Los pasos del algoritmo son los siguientes:
1) Primero, suponga que el número en A [1] es el más pequeño y observe la posición P = 1 en este momento;
2) Compare A[P] y A[I] en secuencia (I cambia de 2 a 10 durante cada comparación, si el número en A[I] es menor que el número en A[P], entonces I El valor). se asigna a P, de modo que P siempre apunta a la posición del número más pequeño actualmente escaneado, es decir, A [P] siempre es igual al número más pequeño de todos los números escaneados. Después de comparar uno por uno, P apunta a la posición del número más pequeño entre los 10 números, es decir, A [P] es el número más pequeño entre los 10 números;
3) Invierta los números de A[P] y A[1], entonces el número más pequeño estará en A[1], es decir, al frente.
Si ahora repite este algoritmo, pero cada vez que lo repite, el rango de la serie que se está comparando se mueve hacia atrás una posición. Es decir, en la segunda comparación, el rango va desde el segundo número hasta el enésimo número. Encuentre la posición P del número más pequeño dentro de este rango y luego intercambie A [P] y A [2], de modo que desde el segundo. El número más pequeño desde el principio hasta el enésimo número está en A [2] tiene éxito, la tercera vez es encontrar el número más pequeño desde el tercer número hasta el enésimo número, y luego intercambiar A [P] y A [3] ... Después de repetir este proceso N-1 veces, simplemente organice los N números en la matriz A de pequeño a grande. Este método de clasificación es la clasificación por selección.
************************************************** * ***************
Descripción del algoritmo de clasificación por inserción:
Al aprender los dos métodos anteriores, puede comprender la idea básica de ordenar y también puede organizar cualquier matriz desordenada de grande a pequeña (orden descendente) o de pequeña a grande (orden ascendente). Ahora supongamos que hay una secuencia de datos ya ordenada y que es necesario insertar un número en esta secuencia de datos ya organizada, pero que la secuencia de datos aún está ordenada después de la inserción. En este momento, se aplicará un nuevo método de clasificación. ser utilizado - Método de 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, para obtener nuevos datos ordenados con el número más uno.
Pregunta: Hay N datos en la matriz A, ordenados de pequeño a grande. Ingrese un número X e inserte el valor de X en la matriz A, de modo que la matriz A insertada todavía esté ordenada de pequeño a grande. .
Entonces el algoritmo para resolver este problema es:
1) Encuentre la posición donde se debe insertar X comparando el tamaño, si se debe colocar en la posición I;
2) Mueva todos los elementos de la matriz a partir de I (incluido I) una posición hacia atrás, es decir, A[I+1]:=A[I];
La clasificación rápida es una mejora con respecto a la clasificación por burbujas. Su idea básica es dividir los datos que se van a ordenar en dos partes independientes mediante una clasificación unidireccional. Todos los datos de una parte son más pequeños que todos los datos de la otra parte, y luego las dos partes de los datos se clasifican secuencialmente. Para una clasificación rápida, todo el proceso de clasificación se puede realizar de forma recursiva, de modo que todos los datos se conviertan en una secuencia ordenada.
Supongamos que la matriz a ordenar es A[1]...A[N]. Primero, seleccione aleatoriamente un dato (generalmente el primer dato) como dato clave y luego coloque todos los números mayores delante de él. y todos los números mayores que él. Los números grandes se colocan detrás de él. Este proceso se llama clasificación rápida. El algoritmo para la clasificación rápida es:
1) Establezca dos variables I y J. Cuando comienza la clasificación, I:=1, J:=N;
2) Utilice el primer elemento de la matriz como datos clave y asígnelo a X, es decir, X:=A[1];
3) Buscar hacia adelante desde J, es decir, buscar hacia adelante desde atrás (J: = J-1), encontrar el primer valor menor que X e intercambiar los dos;
4) Buscar hacia atrás desde I, es decir, buscar de adelante hacia atrás (I: = I + 1), encontrar el primer valor mayor que X e intercambiar los dos;
5) Repetir los pasos 3 y 4 hasta I=J;
Por ejemplo: los valores de la matriz A a ordenar son: (datos clave iniciales X:=49)
A[1] A[2] A[3] A[4] A[5] A[6] A[7]:
49 38 65 97 76 13 27
Después del primer intercambio: 27 38 65 97 76 13 49
(Después de buscar desde atrás según el tercer paso del algoritmo para el segundo intercambio: 27 38 49 97 76 13 65
(Siga el cuarto paso del algoritmo y comience desde el frente para encontrar el valor>
Después del tercer intercambio: 27 38 13 97 76 49 65
(Según el quinto paso del algoritmo, el tercer paso del algoritmo se ejecutará nuevamente desde el final para encontrar el cuarto intercambio: 27 38 13 49 76 97 65
(Siga el cuarto paso del algoritmo y comience desde el frente para encontrar un valor mayor que X, 97>49, intercambie los dos, en este momento J: = 4)
En este momento, al ejecutar el tercer paso, se encuentra que I = J, finalizando así la clasificación rápida. El resultado después de la clasificación rápida es: 27 38 13 49 76 97 65, es decir, todos los números mayores a 49 están en 49. , por lo que los números menores que 49 están todos delante de 49.
La clasificación rápida consiste en llamar a este proceso de forma recursiva: dividir la secuencia de datos con 49 como punto medio, realizar una clasificación rápida similar en la parte frontal y posterior respectivamente, completando así la clasificación rápida de toda la secuencia de datos y finalmente girar la secuencia de datos. en una secuencia ordenada Según esta idea, todo el proceso de clasificación rápida de la matriz A anterior se muestra en la Figura 6:
Estado inicial {49 38 65 97 76 13 27}
Después de una clasificación rápida, se divide en {27 38 13} 49 {76 97 65}
Ordene rápidamente las partes delantera y trasera respectivamente {13} 27 {38}
fin fin {49 65} 76 {97} 49 {65} fin fin
************************************************** * *************************
Figura 6 Descripción del algoritmo de clasificación rápida durante todo el proceso de clasificación rápida
1) Supongamos que N (asumiendo N = 10) números están almacenados en la matriz S;
2), en S[1. . Tome cualquier elemento en N] como base de comparación, por ejemplo, tome T = S [1]. El propósito inicial es determinar la posición K donde debería estar T en el resultado de la clasificación. . . K-1]<=S[K]<=S[K+1..N], es decir, los números antes de S[K] son todos más pequeños que S[K], y los números después de S[K] son todos mayores que S[ K];
3) El uso de la idea de divide y vencerás (es decir, la estrategia de hacer pequeños y grandes) puede mejorar aún más S [1. . K-1] y S[K+1. . N] Luego, los dos conjuntos de datos se ordenan rápidamente hasta que solo hay un dato en el objeto de agrupación.
Si los datos específicos son los siguientes, entonces el primer proceso de clasificación rápido es:
Subíndice de matriz: 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
yo
(1) 36 36 18 53 72 30 48 93 15 45
(2) 36 36 18 45 72 30 48 93 15 53
(3) 36 36 18 15 72 30 48 93 45 53
(4) 36 36 18 15 45 30 48 93 72 53
(5) 36 36 18 15 30 45 48 93 72 53