Insertion d'un nombre dans un tableau trié!

Question

Je voudrais écrire un morceau de code pour insérer un numéro dans un tableau trié à la position appropriée (à savoir le tableau doit encore rester triés après l'insertion)

Ma structure de données ne permet pas de doublons.

Je prévois de faire quelque chose comme ceci:

1. Trouver l'index droit où je consacrions cet élément en utilisant la recherche binaire
2. Créer un espace pour cet élément, en déplaçant tous les éléments de cet indice vers le bas.
3. Mettez cet élément là.

Existe-t-il un autre moyen?

Answer 1

Si vous avez vraiment un tableau et pas une meilleure structure de données, c'est optimal. Si vous êtes flexible sur la mise en œuvre, jetez un oeil à AA Trees - Ils sont plutôt rapides et faciles à mettre en œuvre. Évidemment, prend plus d'espace que le tableau, et cela ne vaut pas la peine si le nombre d'éléments n'est pas assez grand pour remarquer la lenteur du blit par rapport à la magie du pointeur.

Answer 2

Une implémentation d'un arbre basée sur le tas serait plus efficace si vous insériez un grand nombre d'éléments - log n pour les opérations de localisation/suppression et d'insertion.

Answer 3

Les données doivent-elles être triées complètement tout le temps? Si ce n'est pas le cas, s'il est seulement nécessaire d'accéder rapidement à l'élément le plus petit ou le plus élevé, Binary Heap donne le temps d'accès constant et le temps d'addition et de suppression de la connexion. Plus il peut satisfaire votre condition que la mémoire devrait être consécutive, puisque vous pouvez implémenter un BinaryHeap au-dessus d'un tableau (I.e; array [2n + 1] left child, array [2n + 2] right child).