Considérons d’abord comment fusionner deux séquences ordonnées. C'est très simple : comparez simplement le premier numéro des deux séquences et prenez d'abord le plus petit. Après l'avoir pris, supprimez le numéro dans la séquence correspondante. Comparez-les ensuite si l’une des colonnes est vide, supprimez simplement les données de l’autre colonne une par une.
Copiez le code comme suit :
Voir le code
//Fusionner les tableaux ordonnés a[] et b[] en c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int je, j, k;
je = j = k = 0 ;
tandis que (i < n && j < m)
{
si (a[i] < b[j])
c[k++] = a[i++];
autre
c[k++] = b[j++];
}
tandis que (i < n)
c[k++] = a[i++];
tandis que (j < m)
c[k++] = b[j++];
}
On peut voir que l’efficacité de la fusion de séquences ordonnées est relativement élevée et peut atteindre O(n).
Après avoir résolu le problème ci-dessus de fusion de séquences ordonnées, examinons le tri par fusion. L'idée de base est de diviser le tableau en deux groupes A et B. Si les données de ces deux groupes sont toutes ordonnées, alors ces deux ensembles peuvent être facilement résolus. des données sont triées. Comment conserver les données de ces deux groupes en ordre ?
Les groupes A et B peuvent être divisés en deux groupes. Par analogie, lorsque le groupe séparé ne comporte qu'une seule donnée, on peut considérer que le groupe est en ordre, et alors les deux groupes adjacents peuvent être fusionnés. De cette manière, le tri par fusion est effectué en décomposant d'abord le tableau de manière récursive, puis en fusionnant le tableau.
Copiez le code comme suit :
Voir le code
//Fusionnera deux séquences ordonnées a[first...mid] et a[mid...last].
void mergearray (int a[], int premier, int milieu, int dernier, int temp[])
{
int i = premier, j = milieu + 1 ;
int m = milieu, n = dernier ;
entier k = 0 ;
tandis que (i <= m && j <= n)
{
si (a[i] <= a[j])
temp[k++] = a[i++];
autre
temp[k++] = a[j++];
}
tandis que (je <= m)
temp[k++] = a[i++];
tandis que (j <= n)
temp[k++] = a[j++];
pour (je = 0; je < k; je++)
a[premier + i] = temp[i];
}
void mergesort (int a[], int premier, int dernier, int temp[])
{
si (premier <dernier)
{
int mid = (premier + dernier) / 2;
mergesort(a, first, mid, temp); //Le côté gauche est trié
mergesort(a, mid + 1, last, temp); //Le côté droit est trié
mergearray(a, first, mid, last, temp); //Fusionner les deux tableaux ordonnés
}
}
bool MergeSort (int a[], int n)
{
int *p = nouveau int[n];
si (p == NULL)
renvoie faux ;
tri par fusion (a, 0, n - 1, p);
supprimer[] p;
renvoie vrai ;
}
L'efficacité du tri par fusion est relativement élevée. Supposons que la longueur de la séquence soit N. Il faut logN étapes pour diviser la séquence en séquences décimales. Chaque étape est un processus de fusion de la séquence ordonnée. La complexité temporelle peut être enregistrée sous la forme O(. N), donc le total est O(N*logN). Étant donné que le tri par fusion fonctionne à chaque fois sur des données adjacentes, plusieurs méthodes de tri par fusion (tri rapide, tri par fusion, tri Hill, tri par tas) dans O(N*logN) sont également relativement efficaces.