La 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 subsecuencias ordenadas se combinan en la secuencia ordenada general.
La clasificación de fusión es un algoritmo de clasificación efectivo basado en la operación de fusión. Este algoritmo es una aplicación muy típica de divide y conquista. Fusionar las subsecuencias ordenadas para obtener una secuencia completamente ordenada; Si dos tablas ordenadas se fusionan en una tabla ordenada, se llama fusión de 2 vías.
El algoritmo de clasificación de fusión es estable. No es adaptativo y no requiere datos.
Cómo funciona:
1. Solicite espacio para que su tamaño sea la suma de dos secuencias ordenadas, que se utiliza para almacenar las secuencias combinadas
2. Establezca dos punteros, las posiciones iniciales son las posiciones iniciales de las dos secuencias ordenadas respectivamente.
3. Compare los elementos señalados por dos punteros, seleccione elementos relativamente pequeños y póngalos en el espacio de fusión y mueva el puntero a la siguiente posición
4. Repita el paso 3 hasta que un puntero llegue al final de la secuencia
5. Copie todos los elementos restantes de otra secuencia directamente al final de la secuencia fusionada
Ejecutar el código
La copia del código es la siguiente:
paquete com.zc.ManyThread;
import java.util.random;
/**
* Ordenar
* @author soy
*
*/
clase pública Mergesort {
Public static void Mergesort (int [] datos) {
sort (datos, 0, data.length - 1);
}
Public static void sort (int [] data, int izquierdo, int right) {
if (izquierda> = derecho)
devolver;
// Encuentra el índice intermedio
int center = (izquierda + derecha) / 2;
// recursivo la matriz izquierda
ordenar (datos, izquierda, centro);
// recursivo la matriz correcta
ordenar (datos, centro + 1, derecho);
// fusionar
fusionar (datos, izquierda, centro, derecha);
imprimir (datos);
}
/**
* Fusionar las dos matrices, fusionar las dos primeras matrices en orden y aún ordenar después de fusionar
*
* @param datos
* Objeto de matriz
* @param se fue
* Índice del primer elemento de la matriz izquierda
* @Param Center
* El índice del último elemento de la matriz izquierda, Center+1 es el índice del primer elemento de la matriz derecha
* @param correcto
* Índice del último elemento de la matriz correcta
*/
Public static void fuse (int [] data, int izquierdo, int centro, int right) {
// matriz temporal
int [] tmParr = new int [data.length];
// índice del primer elemento de la matriz correcta
int mid = centro + 1;
// tercero registro el índice de la matriz temporal
int terct = izquierda;
// caché el índice del primer elemento de la matriz izquierda
int tmp = izquierda;
while (left <= center && mid <= right) {
// Saque el más pequeño de las dos matrices y póngalo en la matriz temporal
if (data [izquierda] <= data [mid]) {
tmParr [tercero ++] = data [izquierda ++];
} demás {
tmParr [tercero ++] = data [Mid ++];
}
}
// Ponga las partes restantes en la matriz temporal a su vez (de hecho, solo una de las dos se ejecutará)
while (mid <= right) {
tmParr [tercero ++] = data [Mid ++];
}
while (izquierda <= centro) {
tmParr [tercero ++] = data [izquierda ++];
}
// Copiar el contenido de la matriz temporal de regreso a la matriz original
// (el contenido de la gama de derecha izquierda original se copia de nuevo a la matriz original)
while (tmp <= right) {
datos [tmp] = tmParr [tmp ++];
}
}
Public static void print (int [] data) {
para (int i = 0; i <data.length; i ++) {
System.out.print (datos [i] + "/t");
}
System.out.println ();
}
/**
* Generar una matriz aleatoria
* @param cuenta
* @devolver
*/
privado static int [] creatate (int count) {
int [] data = new int [count];
Rand aleatorio = new Random ();
booleano [] bool = nuevo booleano [100];
int num = 0;
para (int i = 0; i <count; i ++) {
hacer {
// Si el número generado es el mismo, continúa en bucle
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
datos [i] = num;
}
devolver datos;
}
public static void main (string [] args) {
int [] data = creatate (10);
imprimir (datos);
MergeSort (datos);
System.out.println ("Array ordenado:");
imprimir (datos);
}
}
Resultados de ejecución:
Lo anterior se trata de este artículo, espero que te pueda gustar.