A Merge é 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 algoritmo de classificação de mesclagem é estável Não é adaptável e não requer dados aleatórios.
Como funciona:
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 combinadas
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 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 mesclada
Execute o código
A cópia do código é a seguinte:
pacote com.zc.manythread;
importar java.util.random;
/**
* Ordenando
* @Author eu sou
*
*/
classe pública Mergesort {
public static void Mergesort (int [] dados) {
classificar (dados, 0, data.length - 1);
}
Public Static Void Class
se (esquerda> = direita)
retornar;
// Encontre o índice intermediário
int centro = (esquerda + direita) / 2;
// recursivo a matriz esquerda
classificar (dados, esquerda, centro);
// Recursive a matriz certa
classificar (dados, centro + 1, direita);
// mescla
mesclar (dados, esquerda, centro, direita);
impressão (dados);
}
/**
* Mesclar as duas matrizes, mesclar as duas primeiras matrizes em ordem e ainda pedir após a fusão
*
* Dados @param
* Objeto de matriz
* @param saiu
* Índice do primeiro elemento da matriz esquerda
* @param Center
* O índice do último elemento da matriz esquerda, Center+1 é o índice do primeiro elemento da matriz direita
* @param certo
* Índice do último elemento da matriz certa
*/
public static void mescle (int [] dados, int esquerda, int centro, int direita) {
// Matriz temporária
int [] tmparr = new int [data.length];
// Índice do primeiro elemento da matriz certa
int mid = Center + 1;
// terceiro registro o índice da matriz temporária
int terceiro = esquerda;
// cache o índice do primeiro elemento da matriz esquerda
int tmp = esquerda;
while (esquerda <= Center && MID <= direita) {
// Retire o menor das duas matrizes e coloque -a na matriz temporária
if (dados [esquerda] <= dados [mid]) {
tmparr [terceiro ++] = dados [esquerda ++];
} outro {
tmparr [terceiro ++] = dados [mid ++];
}
}
// coloque as peças restantes na matriz temporária por sua vez (de fato, apenas uma dos dois enquanto será executada)
while (mid <= direita) {
tmparr [terceiro ++] = dados [mid ++];
}
while (esquerda <= Center) {
tmparr [terceiro ++] = dados [esquerda ++];
}
// Copie o conteúdo da matriz temporária de volta à matriz original
// (o conteúdo da linha esquerda-direita original é copiado de volta à matriz original)
while (tmp <= direita) {
dados [tmp] = tmparr [tmp ++];
}
}
public static void Print (int [] dados) {
for (int i = 0; i <data.length; i ++) {
System.out.print (dados [i] + "/t");
}
System.out.println ();
}
/**
* Gerar uma matriz aleatória
* @param count
* @retornar
*/
private static int [] criado (int conting) {
int [] dados = new int [count];
Rand aleatório = novo aleatório ();
booleano [] bool = novo booleano [100];
int num = 0;
for (int i = 0; i <contagem; i ++) {
fazer {
// Se o número gerado for o mesmo, continue a fazer um loop
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
dados [i] = num;
}
retornar dados;
}
public static void main (string [] args) {
int [] dados = criado (10);
impressão (dados);
misturgesort (dados);
System.out.println ("Array classificado:");
impressão (dados);
}
}
Resultados em execução:
O exposto acima é tudo sobre este artigo, espero que você possa gostar.