Tri d'une liste liée dans Java

J'ai écrit une bulle algorithme de tri pour trier une liste liée. Je suis un Java débutant et essayer d'apprendre les structures de données. Je ne sais pas pourquoi mon second élément n'est pas triés correctement.

MODIFIER

class SListNode {
  Object item;
  SListNode next;


  SListNode(Object obj) {
    item = obj;
    next = null;
  }


  SListNode(Object obj, SListNode next) {
    item = obj;
    this.next = next;
  }

}
public class SList {

    private SListNode head;
    private SListNode temp;

    public void sortList() {
        SListNode node = head,i,j;
        head = node;
        i = node;
        j = node.next;
        while(i.next != null) {
            while(j.next != null) {
                if((Integer)i.item < (Integer)j.item) {
                    temp = i.next;
                    i.next = j.next;
                    j.next = temp;
                 }
                j = j.next;
            }
            i = i.next;
        }
    }
}

C'est la sortie, je suis

List after construction: [  3  6  9  4  12  15  ]
After sorting: [  3  4  9  12  6  15  ]

D'ailleurs je sais le pire des cas d'un tri à bulles est O(n2). Puis-je utiliser mergesort sur une liste, pour avoir un meilleur temps de la complexité?

Merci!

Qu'est-ce que SListNode? Pensez à publier de mise en œuvre.
Sans répondre directement à, la voie à étudier serait de Système..println() de votre liste après chaque swap et après chaque boucle externe pour voir ce qui se passe.

OriginalL'auteur user525146 | 2012-01-24

  1. 7

    Il existe de nombreux algorithmes de tri qui travaillent sur les listes chaînées et mergesort fonctionne très bien dans ce cas. J'ai écrit une précédente réponse à une question sur le tri des listes liées qui explore de nombreux classiques algorithmes de tri sur les listes liées, ainsi que de leur temps et de l'espace de complexité. Vous pouvez utiliser le tri par insertion, tri de sélection, mergesort, et quicksort sur les listes chaînées. Avec un peu de fausser, vous pouvez également obtenir heapsort de travail. Mon vieux répondre a des détails sur la façon de le faire.

    En ce qui concerne votre code, vous remarquerez que dans votre boucle, vous l'avance j de l'avant jusqu'à ce que le next pointeur devient null. À ce stade, vous n'avez jamais réinitialiser j être quelque chose d'autre, donc à chaque itération de la boucle externe à l'intérieur de la boucle ne s'exécute jamais. Vous devriez probablement j = i.next au début de chaque itération. En outre, vous ne voulez probablement pas à avoir la boucle s'arrête lorsque j.next est nulle, mais plutôt quand j est nul, car sinon vous passer le dernier élément du tableau.

    En outre, l'algorithme de tri que vous avez écrit ici est tri de la sélection plutôt que de tri à bulles, parce que vous êtes à faire plusieurs passages sur la liste liée à la recherche pour le plus petit élément que vous n'avez pas encore positionné. Je ne sais pas si c'est un problème ou pas, mais je ne savais pas si vous étiez au courant de cela. Cela dit, je pense que c'est probablement une bonne chose, puisque de tri à bulles est moins efficace que le tri de la sélection dans la plupart des cas (sauf si la liste est déjà triée).

    Espérons que cette aide!

    N'est-ce pas le tri de la Sélection de placer la valeur minimale, en premier lieu, et d'itération sur l'ensemble de la liste?
    Oui, c'est correct, mais qu'est ce que votre code est actuellement en train de faire. 🙂 C'est pas tout à fait la même chose parce que ce que vous faites est constamment à la permutation des éléments les plus petits vers le bas dans la première position, mais il a le même effet net (à chaque itération, l'élément stocké dans i aura la plus faible des valeurs restantes). Tri à bulles est à plusieurs reprises la permutation de paires adjacentes d'éléments qui sont hors de l'endroit jusqu'à ce que plus les swaps sont effectués, mais ton code ne fait pas ça.
    Il ya quelque chose de mal dans mon swap de la boucle. Les résultats ne sont pas d'être échangé. Avant la boucle interne, j'ai ajouté j=i.prochaine. J'ai imprimé les résultats dans la boucle après la fonction d'échange et semble comme sa ne fonctionne pas.

    OriginalL'auteur