Visão geral
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 mescladas na sequência geral ordenada.
A classificação de mesclagem é implementada usando a recursão, que pertence a "dividir e conquistar". A matriz de destino é dividida em duas do meio e, em seguida, as duas matrizes são classificadas separadamente. Depois que a classificação é concluída, as duas matrizes são "mescladas" juntas. A coisa mais importante na classificação de mesclagem é o processo de "mesclagem". No processo de mesclagem, é necessário espaço adicional consistente com as duas matrizes que precisam ser mescladas.
Imagem de reprodução:
etapa
Aplique espaço para que seu tamanho seja a soma de duas seqüências classificadas. Este espaço é usado para armazenar a sequência mesclada para definir dois ponteiros. A posição inicial é a posição inicial das duas seqüências classificadas, compare os elementos apontados pelos dois ponteiros, selecione elementos relativamente pequenos e os coloque no espaço mesclado e mova o ponteiro para a próxima posição. Repita a etapa 3 até que um ponteiro chegue ao final da sequência. Copie todos os elementos restantes da outra sequência diretamente para o final da sequência mesclada.
Dados brutos:
3 5 2 6 2
O pré -requisito para a fusão é separar as matrizes, dividi -las em duas e depois dividi -las em duas, e elas não podem ser divididas novamente e mesclá -las.
A primeira rodada é separada, o índice 2 ((0+4)/2 = 2) é o meio
[3 5 2] [6 2]
A segunda rodada de separação, separa [3 5 2]
[3 5] [2] [6 2]
A terceira rodada de separação, separa [3 5]
[3] [5] [2] [6 2]
Mesclar [3] [5]
[3 5] [2] [6 2]
Mesclar [3 5] [2]
[2 3 5] [6 2]
A quarta rodada é separada, separa [6 2]
[2 3 5] [6] [2]
Mesclar [6] [2]
[2 3 5] [2 6]
Mesclar [2 3 5] [2 6]
[2 2 3 5 6]
Implementação de código (Java)
pacote com.coder4j.main.arithmetic.sorting; classe pública Merge {private static int mark = 0; / ** * Mesclar classificar * * @param Array * @param low * @param alto * @return * / private static int [] classy (int [] matriz, int baixo, int alto) {int mid = (baixo + alto) / 2; if (baixo <alto) {mark ++; System.out.println ("tiro em andamento" + mark + "separação subsequente, get"); System.out.println ("[" + Low + "-" + MID + "] [" + (MID + 1) + "-" + High + "]"); // a matriz esquerda (matriz, baixa, meados); // a matriz certa (matriz, meio + 1, alta); // a mesclagem esquerda e direita (matriz, baixa, média, alta); } retornar a matriz; } / ** * Mesclar a matriz * * @param Array * @param Low * @param MID * @param High * / private estático void Merge (Int [] Array, int baixo, int mid, int High) {System.out.println ("Merge: [" + Low + " +" + Mid + "] e (" + (Mid 1) int [] temp = novo int [alto - baixo + 1]; int i = baixo; // ponteiro esquerdo int j = mid + 1; // ponteiro direito int k = 0; // mova o número menor para a nova matriz primeiro enquanto (i <= mid && j <= alta) {if (array [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // pode haver elementos restantes em uma das duas matrizes // mova o número restante à esquerda para a matriz enquanto (i <= mid) {temp [k ++] = matriz [i ++]; } // mova o número restante à direita para a matriz enquanto (j <= alta) {temp [k ++] = array [j ++]; } // substitua os números na nova matriz de matriz para (int m = 0; m <temp.length; m ++) {array [m+low] = temp [m]; }} / ** * Mesclar classificar * * @param Array * @return * / public static int [] sort (int [] array) {return stit (array, 0, array.length - 1); } public static void main (string [] args) {int [] array = {3, 5, 2, 6, 2}; int [] classificado = classificar (matriz); System.out.println ("resultado final"); para (int i: classificado) {System.out.print (i + ""); }}}Resultados da saída de teste:
A primeira separação está sendo realizada, e o [0-2] [3-4] está sendo realizado e a segunda separação está sendo realizada, e o [0-1] [2-2] está sendo realizado, e a terceira separação está sendo realizada, e a fusão [0-0] [1-1] está sendo: [0-0] e [1-1] a mesclagem: [0-0] e [1-1] a mesclagem: [0-0] e [1-1] Merge: [0-1] e [2-2] estão [2-2], a fusão: [0-0] e [1-1] a mescla [3-3] [4-4] Merge: [3-3] e [4-4] Merge: [0-2] e [3-4] Resultado final 2 2 3 5 6
Após o teste, é consistente com os resultados no exemplo.