对泛型LinkedList进行排序

Question

我必须对LinkedList进行排序，但我不明白为什么它只对它进行一次排序，然后停止。我很难理解泛型类型以及如何使用它们。我发现的大多数例子都是关于对整数数组进行排序的，但我仍然无法将这些例子转化为我的排序方法。任何能帮助我理解如何分类的东西都将不胜感激。

public void sort() {
    Node<T> current = head;
    while(current != null){
        if(current.getNext()!=null && current.getItem().compareTo(current.getNext().getItem()) < 0){
            T temp = current.getItem();
            current.setItem(current.getNext().getItem());
            current.getNext().setItem(temp);
        }
        current = current.getNext();
    }
    current = head;
}

这是我的LinkedList类

public class LinkedList<T extends Comparable<T>> implements LinkedList161<T> {
   protected Node<T> head;
   protected int size;
   public LinkedList() {
      head = null;
      size = 0;
   }
   public void add(T item, int index) {
       if(index < 0 || index > size){
           throw new IndexOutOfBoundsException("out of bounds");
       }
           if(index == 0){
               head = new Node<T>(item, head);
           }
           else{
               Node<T> current = head;
               for(int i = 0; i < index -1; i ++){
                   current = current.getNext();
               }
               current.setNext(new Node<T>(item, current.getNext()));
           }
           size++;
       } 

   public void addFirst(T item) {
      head = new Node<T>(item, head);
      size++;
   }
   public void addToFront(T item) {
          head = new Node<T>(item, head);
          size++;
       }
       public void addToBack(T item) {
           if(head == null){
               head = new Node<T>(item);
               size++;
           }
           else{
               Node<T> temp = head;
               while(temp.getNext() != null){
                   temp = temp.getNext();
               }
               temp.setNext(new Node<T>(item));
               size++;
           }     
       }
       public void remove(int index) {
          if(index < 0 || index > size){
               System.out.println("Index out of bounds");
          }
          if(index == 0){
              head = head.getNext();
          }else{
              Node<T> current = head;
              for(int i = 0; i < index;i++){
                  current = current.getNext();
              }
              current.setNext(current.getNext().getNext());
          }
          size--;
       }
       public T get(int index){
           Node<T> p = head;
           for(int i = 0; i < index;i++){
               p = p.getNext();
           }
           return p.getItem();
       }
       public void clear() {
            head = null;
            size = 0;
       }
       public int size() {
        return size;
       }
   @Override
   public String toString() {
       String result = "";
       if (head == null)
           return result;
       for (Node<T> p = head; p != null; p = p.getNext()) {
           result += p.getItem() + "n";
       }
       return result.substring(0,result.length()-1); // remove last n
   }
@Override
public void sort() {
    Node<T> current = head;
    for(int i = 0; i < size;i++){
        if(current.getNext()!=null && current.getItem().compareTo(current.getNext().getItem()) < 0){
            T temp = current.getItem();
            current.setItem(current.getNext().getItem());
            current.getNext().setItem(temp);
        }
        current = current.getNext();
    }
    current = head;
}
}

这是我的节点类

public class Node<T> implements Node161<T>{
protected T item;
protected Node<T> next;
public Node(T item, Node<T> next) {
   setItem(item);
   setNext(next);
}
public Node(T item) {
   setItem(item);
}
public T getItem() {
    return item;
}
public void setItem(T i) {
   item = i;
}
public void setNext(Node<T> n) {
   next = n;
}
public Node<T> getNext() {
   return next;
}
@Override
public String toString() {
   return item.toString();
}
}

Answer 1

您的排序实现只执行排序的一步：它对相邻的项目进行排序，经过这一步后情况会好转，但整个集合将不会进行排序。您应该重复此步骤，直到您的集合得到排序。

请注意，此算法不是有效的。您应该考虑一些更复杂的方法，如合并排序

Answer 2

Wiki合并排序文章现在为链表提供了一个简单但快速的自下而上的合并排序，该排序使用指向列表第一个节点的指针的小数组（通常为26到32），其中array[i]要么为null，要么指向大小为2的幂i的列表。与其他一些方法不同，没有扫描列表，该数组与一个通用的合并函数一起使用，该函数合并两个已经排序的列表。文章链接：

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists