A Merge Sort é um algoritmo de classificação eficaz com base na operação de mesclagem. Esse algoritmo é uma aplicação muito típica de dividir e conquistar.
O método de classificação de mesclagem é mesclar duas (ou mais de duas) tabelas ordenadas em uma nova tabela ordenada, ou seja, dividir a sequência a ser classificada em várias subsequências, cada subsequência é ordenada. Em seguida, as subsequências ordenadas são combinadas na sequência geral ordenada.
A classificação de mesclagem é um algoritmo de classificação eficaz com base na operação de mesclagem. Esse algoritmo é uma aplicação muito típica de dividir e conquistar. Mesclar as subseqüências ordenadas para obter uma sequência completamente ordenada; Se duas tabelas ordenadas forem mescladas em uma tabela ordenada, ela é chamada de fusão de duas vias.
O processo de operação de mesclagem é o seguinte:
1. Aplique o espaço para que seu tamanho seja a soma de duas seqüências classificadas, que são usadas para armazenar as seqüências mescladas
2. Defina dois ponteiros, a posição inicial é a posição inicial das duas seqüências classificadas, respectivamente
3. Compare os elementos apontados por dois ponteiros, selecione elementos relativamente pequenos e coloque -os no espaço de mesclagem e mova o ponteiro para a próxima posição
4. Repita a etapa 3 até que um ponteiro chegue ao final da sequência
5. Copie todos os elementos restantes de outra sequência diretamente para o final da sequência de mesclagem
Exemplo 1:
A cópia do código é a seguinte:
/**
* Merge, também conhecido como algoritmo de mesclagem, refere -se à operação de combinar duas seqüências classificadas em uma sequência.
* O algoritmo de classificação de mesclagem depende da operação de mesclagem.
*
* O processo de operação de mesclagem é o seguinte:
*
* 1. Aplique o espaço para que seu tamanho seja a soma de duas seqüências classificadas, que são usadas para armazenar as sequências mescladas
* 2. Defina dois ponteiros, as posições iniciais são as posições iniciais das duas seqüências classificadas, respectivamente
* 3. Compare os elementos apontados pelos dois ponteiros, selecione elementos relativamente pequenos e coloque -os no espaço de mesclagem e mova o ponteiro para a próxima posição
* 4. Repita a etapa 3 até que um ponteiro chegue ao final da sequência
* 5. Copie todos os elementos restantes de outra sequência diretamente para o final da sequência mesclada
*
*/
função mesck (itens) {
if (items.length <2) {
itens de retorno;
}
var médio = math.floor (items.length / 2),
Esquerda = item.slice (0, meio),
direita = items.slice (meio),
params = mescle (Mergesort (esquerda), Mergesort (direita));
params.unShift (0, items.length);
items.splice.apply (itens, params);
itens de retorno;
Função Merge (esquerda, direita) {
var resultado = [],
il = 0,
ir = 0;
while (il Left.length && ir <right.length) {
if (esquerda [il] <direita [ir]) {
resultado.push (esquerda [il ++]);
} outro {
resultado.push (direita [ir ++]);
}
}
retorno resultado.CONCAT (esquerda.slice (IL)) .CONCAT (Right.slice (IR));
}
}
// teste
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mesclar (arr);
Exemplo 2:
A cópia do código é a seguinte:
<script type = "text/javascript">
//document.write("-------------------------------------------- -------------------------------------------------------- ---------------------------
// var array = nova matriz (12, 25, 32, 16, 18, 27, 59, 69, 36);
var count = 0;
// Ligue para o método de classificação para classificar
// msort (matriz, matriz, 0, array.length - 1);
// Matriz de origem de origem
// Matriz de destino de destes
// S Start Subscript
// Ttarget Subscript
função msort (fonte, dest, s, t) {
var resultado = "";
var m; // Tome o valor intermediário
var dest2 = new Array ();
if (s == t) {
dest [s] = fonte [s];
}
outro {
m = math.floor ((S + T) / 2);
msort (fonte, dest2, s, m);
msort (fonte, dest2, m+1, t);
Merge (dest2, dest, s, m, t);
/* Resultado de saída*/
resultado += "<r /> thread" +++ count +"O resultado da ordem através do passe é:";
for (var n = 0; n <dest.length; n ++) {
resultado + = array [n] + ",";
}
/* O resultado da saída termina*/
}
resultado de retorno;
}
/* O resultado da saída termina*/
// fundiu duas matrizes em ordem de pequena a grande
// Origem do Array original
// Matriz classificada de destastes
// STHE Primeiro subscrito
// m a tabela a seguir da segunda matriz
// comprimento ntotal
função mescle (fonte, dest, s, m, n) {
for (var j = m+1, k = s; j <= n && s <= m; k ++) {
if (fonte [s] <fonte [j]) {
dest [k] = fonte [s ++];
}
outro {
dest [k] = fonte [j ++];
}
}
// Adicione as matrizes ordenadas restantes ao final do destes
if (s <= m) {
for (var l = 0; l <= m - s; l ++) {
dest [k + l] = fonte [s + l];
}
}
if (j <= n) {
for (var l = 0; l <= n - j; l ++) {
dest [k + l] = fonte [j + l];
}
}
}
//document.write("<BR /> <BR /> ")
</script>