Étant donné deux tableaux triés A et B, où la fin de A a suffisamment d'espace pour B, écrivez une méthode pour fusionner B dans A et les trier.
Après avoir répondu à cette question, l'idée la plus directe est de comparer les éléments de A et B et de les insérer dans les tableaux dans l'ordre jusqu'à ce que tous les éléments de A et B soient parcourus. Mais cela présente un inconvénient : si la position d'insertion de l'élément est à l'avant du tableau A, le tableau d'origine doit être déplacé vers l'arrière. Cela ajoute des frais généraux. Mais on peut utiliser une autre méthode pour insérer des éléments à la fin du tableau A. De cette façon, aucun élément ne bougera ! Le code est le suivant :
Copiez le code code comme suit : /*
* lastA : le nombre réel d'éléments dans un lastB : le nombre réel d'éléments dans b mergeIndex est la taille réelle de l'espace du nouveau tableau
*/
public static void mergeOrder(int[] a, int[] b, int lastA, int lastB) {
int indexA = dernierA - 1;
int indexB = dernierB - 1;
int mergeIndex = dernierA + dernierB - 1;
tandis que (indexA >= 0 && indexB >= 0) {
si (a[indexA] > b[indexB]) {
a[mergeIndex] = a[indexA];
mergeIndex --;
indexA --;
} autre {
a[mergeIndex] = b[indexB];
mergeIndex --;
indiceB --;
}
}
tandis que (indexB >= 0) {
a[mergeIndex] = b[indexB];
mergeIndex --;
indiceB --;
}
}