Descripción general
El método de clasificación de fusión es fusionar dos (o más de dos) tablas ordenadas en una nueva tabla ordenada, es decir, dividir la secuencia para clasificarse en varias subsecuencias, cada subsecuencia se ordena. Luego, las posteriores ordenadas se fusionan en la secuencia general ordenada.
La clasificación de fusión se implementa utilizando la recursión, que pertenece a "dividir y conquistar". La matriz objetivo se divide en dos desde el medio, y luego las dos matrices se clasifican por separado. Después de completar la clasificación, las dos matrices se "fusionan" juntas. Lo más importante en la clasificación de fusiones es el proceso de "fusión". En el proceso de fusión, se requiere espacio adicional que sea consistente con las dos matrices que deben fusionarse.
Imagen de reproducción:
paso
Aplique espacio para que su tamaño sea la suma de dos secuencias ordenadas. Este espacio se utiliza para almacenar la secuencia fusionada para establecer dos punteros. La posición inicial es la posición inicial de las dos secuencias ordenadas, compare los elementos apuntados por los dos punteros, seleccione elementos relativamente pequeños y colóquelos en el espacio fusionado y mueva el puntero a la siguiente posición. Repita el paso 3 hasta que un puntero llegue al final de la secuencia. Copie todos los elementos restantes de la otra secuencia directamente al final de la secuencia fusionada.
Datos sin procesar:
3 5 2 6 2
El requisito previo para fusionar es separar las matrices, dividirlas en dos y luego dividirlas en dos, y no pueden dividirse nuevamente y fusionarlas.
La primera ronda está separada, el índice 2 ((0+4)/2 = 2) es el medio
[3 5 2] [6 2]
La segunda ronda de separación, separada [3 5 2]
[3 5] [2] [6 2]
La tercera ronda de separación, separado [3 5]
[3] [5] [2] [6 2]
Fusionar [3] [5]
[3 5] [2] [6 2]
Fusionar [3 5] [2]
[2 3 5] [6 2]
La cuarta ronda está separada, se separa [6 2]
[2 3 5] [6] [2]
Fusionar [6] [2]
[2 3 5] [2 6]
Fusionar [2 3 5] [2 6]
[2 2 3 5 6]
Implementación del código (Java)
paquete com.coder4j.main.arithmetic.sorting; public class fusion {private static int mark = 0; / ** * Sort de fusión * * @param Array * @param low * @param high * @return * / private static int [] sort (int [] array, int low, int high) {int mid = (low + high) / 2; if (low <high) {mark ++; System.out.println ("Sillez en progreso" + Mark + "Separación posterior, Get"); System.out.println ("[" + Low + "-" + Mid + "] [" + (Mid + 1) + "-" + High + "]"); // el tipo de matriz izquierda (matriz, baja, mitad); // la clasificación de matriz correcta (matriz, mediana + 1, alta); // la fusión izquierda y derecha (matriz, baja, media, alta); } matriz de retorno; } / ** * fusione la matriz * * @param array * @param low * @param mid * @param high * / private static void merge (int [] array, int low, int mid, int high) {system.out.println ("fusion: [" + low + "-" + mid + "] y [" + (mid + 1) + "-" + high + "]"); int [] temp = new int [alto - bajo + 1]; int i = Low; // Puntero izquierdo int j = Mid + 1; // Pointer derecho int k = 0; // Mueve el número más pequeño a la nueva matriz primero mientras (i <= mid && j <= high) {if (array [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // Puede haber elementos restantes en una de las dos matrices // mover el número restante a la izquierda a la matriz mientras (i <= mid) {temp [k ++] = array [i ++]; } // Mueva el número restante a la derecha a la matriz mientras (j <= high) {temp [k ++] = array [j ++]; } // sobrescribe los números en la nueva matriz de matriz para (int m = 0; m <temp.length; m ++) {array [m+low] = temp [m]; }} / ** * Merge Sort * * @param Array * @return * / public static int [] sort (int [] array) {return sort (array, 0, array.length - 1); } public static void main (string [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sorted = sort (array); System.out.println ("resultado final"); para (int i: sorted) {system.out.print (i + ""); }}}Resultados de la salida de prueba:
Se está realizando la primera separación, y se está realizando [0-2] [3-4], y se está realizando la segunda separación, y se está realizando [0-1] [2-2], y la tercera separación se está realizando, y se está realizando [0-0] [1-1] fusion [3-3] [4-4] Fusionar: [3-3] y [4-4] Fusionar: [0-2] y [3-4] resultado final 2 2 3 5 6
Después de la prueba, es consistente con los resultados en el ejemplo.