Visão geral do algoritmo/idéias
A classificação de mesclagem é baseada em uma estratégia chamada "Divide and Conquer". A idéia básica é a seguinte:
1. Para duas matrizes ordenadas, para mesclá -las em uma matriz ordenada, podemos escrever facilmente o seguinte código:
// Ambos A e B são ascend.Public void Merge (int [] a, int [] b, int [] c) {int i = 0, j = 0, k = 0; while (i <= A.Length && j <= b.length) {if (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} while (i <= A.Length) {c [k ++] = a [i ++]; }} É fácil ver que esse algoritmo de fusão é eficiente e sua complexidade de tempo pode atingir o (n).
2. Se houver uma matriz não ordenada que precise ser classificada, mas seus dois subarrays completamente divididos A e B são ordenados separadamente, também podemos implementá -los facilmente com a ajuda do código acima;
3. Então, o que devo fazer se A e B estiverem desordenados? Você pode dividi -los em matrizes menores.
4. Se você dividi -lo até o menor, cada subarray tem apenas um elemento, ele poderá ser considerado como uma matriz ordenada.
5. Comece com essas menores matrizes, mescla -as contra as etapas acima e toda a matriz está organizada.
Em resumo, a classificação de mesclagem é usar a recursão, primeiro decompor a matriz em um subarray e depois mescla a matriz.
exemplo
Aqui está um exemplo. Se você deseja classificar a matriz A = {2,1,3,5,2,3}, divida a matriz em dois subarrays: {2,1,3} e {5,2,3}. Depois de classificar esses dois subarrays, eles se tornam {1,2,3} e {2,3,5} e, em seguida, mesclam as duas matrizes para obter a matriz de pedidos finais. A implementação do código é a seguinte:
Void Sort (int [] a) {int [] aux = new int [A.Length]; // Aux Array mescleSort (a, 0, A.Length - 1, aux);} void mesmort (int [] a, int lo, int hi, int [] aux) {if (hi <= lo) return; int mid = lo + (hi - lo) / 2; mesclar (A, Lo, Mid, Aux); mesclar (A, Mid + 1, Hi, Aux); mesclar (a, lo, mid, hi, aux);} void mescle (int [] a, int lo, int mid, int hi, int [] aux) {int i = lo, j = mid + 1; for (int k = lo; k <= hi; k ++) {aux [k] = a [k]; } para (int k = lo; k <= hi; k ++) {if (i> mid) a [k] = aux [j ++]; caso contrário, if (j> oi) a [k] = aux [i ++]; caso contrário, if (aux [i] <= aux [j]) a [k] = aux [i ++]; caso contrário, [k] = aux [j ++]; }} Outra implementação: classificação de mesclagem de baixo para cima
Na implementação acima, é equivalente a dividir um grande problema em pequenos problemas e resolvê -los separadamente e, em seguida, usar as respostas para todos os pequenos problemas para resolver todo o grande problema. Dividindo o tipo de uma grande variedade em uma pequena matriz, o tipo de tipo é um tipo de cima para baixo. Há outra implementação que é a classificação de baixo para cima, ou seja, primeiro mescla dois e depois mescla quatro e quatro ... A implementação do código é a seguinte:
Void Sort (int [] a) {int n = A.Length; int [] aux = new int [n]; para (int sz = 1; sz <n; sz + = sz) {for (int lo = 0; lo <n - sz; lo + = sz + sz) {// em cada rodada de mesclagem, a segunda sub -matriz que foi mesclada na última vez que pode ser menor que a primeira sub -matriz (a + sz - 1, 1, 1, 1; }}}