在Java中对链表进行排序 [英] Sorting a linked list in Java

问题描述

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

I have written a bubble sort algorithm to sort a linked list. I am a Java beginner and trying to learn data structures. I am confused why my second element is not sorted properly.

编辑

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 ^2功能）。我可以在链表上使用mergesort以获得更好的时间复杂度吗？

Besides I know the worst case scenario of a bubble sort is O(n²). Can I use mergesort on a linked list to have a better time complexity?

谢谢！

推荐答案

在链接列表中有许多排序算法，在这种情况下，mergesort可以很好地工作。我写了 关于排序链接列表的问题的早期答案 ，它探讨了许多经典排序算法链表，以及它们的时间和空间复杂性。您可以在链接列表上使用插入排序，选择排序，合并输入和快速排序。有点捏造，你也可以让heapsort工作。我的旧答案有关于如何执行此操作的详细信息。

There are many sorting algorithms that work on linked lists and mergesort works excellently in this case. I wrote an earlier answer to a question about sorting linked lists that explores many classic sorting algorithms on linked lists, along with their time and space complexities. You can use insertion sort, selection sort, mergesort, and quicksort on linked lists. With a bit of fudging, you can also get heapsort working. My older answer has details on how to do this.

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

With regards to your code, notice that in your inner loop you advance j forward until the next pointer becomes null. At this point, you never reset j to be anything else, so on each future iteration of the outer loop the inner loop never executes. You should probably set j = i.next at the start of each iteration. Moreover, you probably don't want to have the loop stop when j.next is null, but rather when j is null, since otherwise you skip the last element of the array.

此外，你在这里写的排序算法是 选择排序 而不是冒泡排序，因为您在链表上进行了多次搜索，寻找最小的元素你尚未定位。我不知道这是不是问题，但我不确定你是否意识到这一点。也就是说，我认为这可能是一件好事，因为在大多数情况下，冒泡排序的效率低于选择排序（除非列表已接近排序）。

Additionally, the sorting algorithm you've written here is selection sort rather than bubble sort, because you're making many passes over the linked list looking for the smallest element that you haven't positioned yet. I don't know if this is a problem or not, but I wasn't sure if you were aware of this. That said, I think that's probably a good thing, since bubble sort is less efficient than selection sort in most cases (unless the list is already close to being sorted).

希望这有帮助！

这篇关于在Java中对链表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！