Primero considere cómo fusionar dos secuencias ordenadas. Esto es muy simple. Simplemente compare el primer número de las dos secuencias y tome el más pequeño primero. Después de tomarlo, elimine el número en la secuencia correspondiente. Luego compárelos. Si una de las columnas está vacía, simplemente saque los datos de la otra columna uno por uno.
Copie el código de código de la siguiente manera:
Ver código
//Fusionar matrices ordenadas a[] y b[] en c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
yo = j = k = 0;
mientras (i < n && j < m)
{
si (a[i] <b[j])
c[k++] = a[i++];
demás
c[k++] = b[j++];
}
mientras (i < n)
c[k++] = a[i++];
mientras (j<m)
c[k++] = b[j++];
}
Se puede ver que la eficiencia de fusionar secuencias ordenadas es relativamente alta y puede alcanzar O (n).
Después de resolver el problema anterior de fusionar secuencias ordenadas, veamos la ordenación por fusión. La idea básica es dividir la matriz en dos grupos A y B. Si todos los datos de estos dos grupos están ordenados, entonces se pueden dividir fácilmente Estos dos conjuntos. de datos están ordenados. ¿Cómo mantener en orden los datos de estos dos grupos?
Los grupos A y B se pueden dividir en dos grupos. Por analogía, cuando el grupo separado tiene solo un dato, se puede considerar que el grupo ha alcanzado el orden y luego los dos grupos adyacentes se pueden fusionar. De esta manera, la clasificación por fusión se completa descomponiendo primero la matriz de forma recursiva y luego fusionando la matriz.
Copie el código de código de la siguiente manera:
Ver código
// Fusionará dos secuencias ordenadas a[first...mid] y a[mid...last].
void mergearray(int a[], int primero, int mid, int last, int temp[])
{
int i = primero, j = medio + 1;
int m = medio, n = último;
int k = 0;
mientras (i <= m && j <= n)
{
si (a[i] <= a[j])
temperatura[k++] = a[i++];
demás
temperatura[k++] = a[j++];
}
mientras (yo <= m)
temperatura[k++] = a[i++];
mientras (j <= n)
temperatura[k++] = a[j++];
para (i = 0; i < k; i++)
a[primero + i] = temp[i];
}
void mergesort(int a[], int primero, int último, int temp[])
{
si (primero <último)
{
int mid = (primero + último) / 2;
mergesort(a, first, mid, temp); //El lado izquierdo está ordenado
mergesort(a, mid + 1, last, temp); //El lado derecho está ordenado.
mergearray(a, first, mid, last, temp); //Fusiona las dos matrices ordenadas.
}
}
bool MergeSort(int a[], int n)
{
int *p = nuevo int[n];
si (p == NULO)
devolver falso;
mergesort(a, 0, n - 1, p);
eliminar[]p;
devolver verdadero;
}
La eficiencia de la clasificación por fusión es relativamente alta. Suponga que la longitud de la secuencia es N. Se necesitan logN pasos para dividir la secuencia en secuencias decimales. Cada paso es un proceso de fusión de la secuencia ordenada. La complejidad del tiempo se puede registrar como O (. N), por lo que el total es O(N*logN). Debido a que la clasificación por fusión opera en datos adyacentes cada vez, varios métodos de clasificación de clasificación por fusión (clasificación rápida, clasificación por fusión, clasificación Hill, clasificación en montón) en O (N * logN) también son relativamente eficientes.