Insertion dans une liste triée

Avec Java, j'ai une classe, connu comme TestClass, qui a un membre nommé du Nom, qui est une chaîne de caractères. J'ai aussi une liste de tableaux de ce type, qui est déjà triée par ordre alphabétique des noms. Ce que je veux faire est de trouver le meilleur indice pour mettre une nouvelle instance de TestClass. La meilleure approche, j'ai pu arriver jusqu'ici est: est-ce

public static int findBestIndex(char entry, ArrayList<TestClass> list){
int desiredIndex = -1;
int oldPivot = list.size();
int pivot = list.size()/2;
do
{
char test = list.get(pivot).Name.charAt(0);
if (test == entry)
{
desiredIndex = pivot;
}
else if (Math.abs(oldPivot - pivot) <= 1)
{
if (test < entry)
{
desiredIndex = pivot + 1;
}
else
{
desiredIndex = pivot - 1;
}
}
else if (test < entry)
{
int tempPiv = pivot;
pivot = oldPivot - (oldPivot - pivot)/2;
oldPivot = tempPiv;
}
else
{
int tempPiv = pivot;
pivot = pivot - (oldPivot - pivot)/2;
oldPivot = tempPiv;
}
} while (desiredIndex < 0);
return desiredIndex;
}

Essentiellement, Briser le tableau en deux, vérifier pour voir si votre valeur se passe avant, après, ou à ce point. Si c'est après, cochez la première moitié du tableau. Autres sage, cochez la seconde moitié. Ensuite, répétez. Je comprends que cette méthode ne teste que par le premier caractère, mais c'est facilement résolu, et n'est pas adapté à mon problème principal. Pour certains cas, cette approche fonctionne assez bien. Pour la plupart, il fonctionne très mal. Je suppose que ce n'est pas la recherche d'un nouveau point de pivot correctement, et si c'est le cas, comment pourrais-je résoudre ce problème?

Edit: Pour plus de précisions, je suis en utilisant ce pour un système d'inventaire, donc je ne suis pas sûr qu'un LinkedList serait approprié. Je suis à l'aide d'une liste de tableaux parce qu'ils sont plus familiers pour moi, et serait ainsi plus facile à traduire dans une autre langue, si nécessaire (ce qui est probable, à l'heure actuelle, pourrait être le déplacement de plus de C#). J'essaie d'éviter des choses comme Comparables pour cette raison, comme je l'avais complètement ré-écrire si C# n'en a pas.

Modifier la partie Duex: Compris ce que je faisais mal. Au lieu d'utiliser le précédent point de pivot, j'aurais été de la définition et la modification des frontières de la région, j'ai été vérifier, et la création du nouveau pivot sur cette base.

  • Pourquoi ne pas vous suffit d'insérer tous les éléments, puis utilisez Collections.sort()?
  • Peut-être que je ne suis pas à la recherche à ce droit, mais si vous déterminez que la valeur va après les sélectionné (test) le point, n'est-ce pas vérifier la deuxième moitié du tableau?
  • recours après chaque insertion serait susceptible d'être le plus lent de chemin à faire, bien que la vitesse n'est pas mon plus gros souci, car il n'y aura probablement pas beaucoup d'objets décalés et sortir rapidement.
  • c'est ce que j'essayais de faire, mais probablement ma tentative de le faire c'était complètement faux, et c'est là que je vais avoir le problème.
  • il dépend de la fréquence de cette liste triée est accessible. Si pas souvent que vous pouvez simplement reconstruire cette liste en cas de besoin.
InformationsquelleAutor user2423158 | 2013-05-26