Merge Sort 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.
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 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 proceso de operación de fusión es el siguiente:
1. Solicite espacio para que su tamaño sea la suma de dos secuencias ordenadas, que se utiliza para almacenar las secuencias fusionadas
2. Establezca dos punteros, la posición inicial es la posición inicial 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 de fusión
Ejemplo 1:
La copia del código es la siguiente:
/**
* La fusión, también conocida como algoritmo de fusión, se refiere a la operación de combinar dos secuencias ordenadas en una secuencia.
* El algoritmo de clasificación de fusión depende de la operación de fusión.
*
* El proceso de operación de fusión es el siguiente:
*
* 1. Solicite espacio para que su tamaño sea la suma de dos secuencias ordenadas, que se utiliza para almacenar las secuencias fusionadas
* 2. Establezca dos punteros, las posiciones iniciales son las posiciones iniciales de las dos secuencias ordenadas respectivamente
* 3. Compare los elementos señalados por los dos punteros, seleccione elementos relativamente pequeños y colóquelos 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
*
*/
función mergeort (elementos) {
if (items.length <2) {
devolver elementos;
}
var middle = Math.floor (elementos.length / 2),
izquierda = items.lice (0, medio),
right = items.lice (medio),
params = fusión (Mergesort (izquierda), Mergesort (derecha));
params.unshift (0, items.length);
items.splice.apply (elementos, parámetros);
devolver elementos;
Función fusionar (izquierda, derecha) {
resultado var = [],
IL = 0,
ir = 0;
while (il <left.length && ir <right.length) {
if (izquierda [il] <derecha [ir]) {
resultado.push (izquierda [IL ++]);
} demás {
resultado.push (derecho [ir ++]);
}
}
return resultado.concat (left.slice (il)) .concat (right.slice (ir));
}
}
// prueba
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Mergesort (arr);
Ejemplo 2:
La copia del código es la siguiente:
<script type = "text/javaScript">
//document.write("------------------------------------------ -------------------------------------------------- ----------------------------------------);
// Var Array = nueva matriz (12, 25, 32, 16, 18, 27, 59, 69, 36);
Var Count = 0;
// llame al método de clasificación para clasificar
// msort (matriz, matriz, 0, array.length - 1);
// matriz de origen
// matriz de destino
// s Subíndico inicial
// subíndice ttarget
función msort (fuente, des, s, t) {
resultado var = "";
var m;
var dest2 = new Array ();
if (s == t) {
des [s] = fuente [s];
}
demás {
m = Math.floor ((S + T) / 2);
MSORT (fuente, Dest2, S, M);
MSORT (fuente, Dest2, M+1, T);
fusionar (Dest2, Dest, S, M, T);
/* Resultado de salida*/
Result += "<Br /> Hilo" +++ Count +"El resultado del orden del pase es:";
para (var n = 0; n <dest.length; n ++) {
resultado + = array [n] + ",";
}
/* El resultado de salida termina*/
}
resultado de retorno;
}
/* El resultado de salida termina*/
// fusionó dos matrices en orden de pequeño a grande
// matriz original de fuente
// matriz ordenada
// sthe primer subíndice
// m la siguiente tabla de la segunda matriz
// longitud ntotal
Function Merge (Fuente, Dest, S, M, N) {
para (var j = m+1, k = s; j <= n && s <= m; k ++) {
if (fuente [s] <fuente [j]) {
des [k] = fuente [S ++];
}
demás {
des [k] = fuente [j ++];
}
}
// Agregar las matrices ordenadas restantes al final del Dest
if (s <= m) {
para (var l = 0; l <= m - s; l ++) {
des [k + l] = fuente [S + L];
}
}
if (j <= n) {
para (var l = 0; l <= n - j; l ++) {
des [k + l] = fuente [j + l];
}
}
}
//document.write("<br /> <Br /> ")
</script>