Primeiro considere como mesclar duas sequências ordenadas. Isso é muito simples. Basta comparar o primeiro número das duas sequências e pegar o menor primeiro. Depois de pegá-lo, exclua o número na sequência correspondente. Em seguida, compare-os. Se uma das colunas estiver vazia, basta retirar os dados da outra coluna, um por um.
Copie o código do código da seguinte forma:
Ver código
//Mesclar arrays ordenados a[] e b[] em c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int eu, j, k;
eu = j = k = 0;
enquanto (eu <n && j <m)
{
se (a[i] <b[j])
c[k++] = a[i++];
outro
c[k++] = b[j++];
}
enquanto (eu <n)
c[k++] = a[i++];
enquanto (j <m)
c[k++] = b[j++];
}
Pode-se observar que a eficiência da fusão de sequências ordenadas é relativamente alta e pode atingir O(n).
Depois de resolver o problema acima de mesclar sequências ordenadas, vamos dar uma olhada na classificação por mesclagem. A ideia básica é dividir a matriz em dois grupos A e B. Se os dados nesses dois grupos estiverem todos ordenados, então pode ser facilmente Esses dois conjuntos. de dados são classificados. Como manter os dados desses dois grupos em ordem?
Os grupos A e B podem ser divididos em dois grupos. Por analogia, quando o grupo separado possui apenas um dado, pode-se considerar que o grupo atingiu a ordem, e então os dois grupos adjacentes podem ser mesclados. Dessa forma, a classificação por mesclagem é concluída primeiro decompondo o array recursivamente e depois mesclando o array.
Copie o código do código da seguinte forma:
Ver código
//Irá mesclar duas sequências ordenadas a[first...mid] e a[mid...last].
void mergearray(int a[], int primeiro, int meio, int último, int temp[])
{
int i = primeiro, j = meio + 1;
int m = meio, n = último;
int k = 0;
enquanto (eu <= m && j <= n)
{
se (a[i] <= a[j])
temp[k++] = a[i++];
outro
temp[k++] = a[j++];
}
enquanto (eu <= m)
temp[k++] = a[i++];
enquanto (j <= n)
temp[k++] = a[j++];
para (eu = 0; eu <k; eu++)
a[primeiro + i] = temp[i];
}
void mergesort(int a[], int primeiro, int último, int temp[])
{
if (primeiro <último)
{
int meio = (primeiro + último)/2;
mergesort(a, first, mid, temp); //O lado esquerdo é classificado
mergesort(a, mid + 1, last, temp); //O lado direito é classificado
mergearray(a, first, mid, last, temp); //Mescla os dois arrays ordenados
}
}
bool MergeSort(int a[], int n)
{
int *p = novo int[n];
se (p == NULO)
retornar falso;
mesclarsort(a, 0, n - 1, p);
excluir[] p;
retornar verdadeiro;
}
A eficiência da classificação por mesclagem é relativamente alta. Suponha que o comprimento da sequência seja N. São necessárias logN etapas para dividir a sequência em sequências decimais. Cada etapa é um processo de mesclagem da sequência ordenada. N), então o total é O(N*logN). Como a classificação por mesclagem opera sempre em dados adjacentes, vários métodos de classificação de classificação por mesclagem (classificação rápida, classificação por mesclagem, classificação por colina, classificação por heap) em O (N * logN) também são relativamente eficientes.