在Java中对链表进行排序

Question

我编写了一个冒泡排序算法来对链表进行排序.我是Java初学者并且正在尝试学习数据结构.我很困惑为什么我的第二个元素没有正确排序.

编辑

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;
        }
    }
}

这是我得到的输出

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

此外,我知道冒泡排序的最坏情况是O(n ²).我可以在链表上使用mergesort以获得更好的时间复杂度吗？

谢谢!

Answer 1

在这种情况下,有很多排序算法可以处理链表,而mergesort可以很好地工作.我写了一个关于排序链表的问题的早期答案,该链表在链表上探讨了许多经典的排序算法,以及它们的时间和空间复杂性.您可以在链接列表上使用插入排序,选择排序,合并输入和快速排序.有点捏造,你也可以让heapsort工作.我的老答案详细说明了如何做到这一点.

关于你的代码,请注意在你的内循环中你向前j推进直到next指针变为null.此时,您永远不会重置j为其他任何东西,因此在外部循环的每个未来迭代中,内部循环永远不会执行.您应该j = i.next在每次迭代开始时设置.此外,您可能不希望在j.nextnull为空时停止循环,而是在j为null时,因为否则您跳过数组的最后一个元素.

此外,您在此处编写的排序算法是选择排序而不是冒泡排序,因为您在链接列表上进行了多次传递,以查找尚未定位的最小元素.我不知道这是不是问题,但我不确定你是否意识到这一点.也就是说,我认为这可能是一件好事,因为在大多数情况下,冒泡排序的效率低于选择排序(除非列表已经接近排序).

希望这可以帮助!