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²)。我可以在链表上使用归并排序以获得更好的时间复杂度吗？

Answer 1

有许多排序算法适用于链表，合并排序在这种情况下表现出色。我写了 an earlier answer to a question about sorting linked lists 探讨了链表上的许多经典排序算法，以及它们的时间和空间复杂性。您可以在链表上使用插入排序、选择排序、归并排序和快速排序。通过一些捏造，您还可以使堆排序工作。我的旧答案详细说明了如何执行此操作。

关于您的代码，请注意，在您的内部循环中，您将 j 向前推进，直到 next 指针变为 null。此时，您永远不会将 j 重置为任何其他内容，因此在外循环的每次 future 迭代中，内循环永远不会执行。您可能应该在每次迭代开始时设置 j = i.next。此外，您可能不想在 j.next 为空时停止循环，而是在 j 为空时停止循环，否则您将跳过数组。

此外，您在此处编写的排序算法是 selection sort 而不是冒泡排序，因为您要遍历链接列表以寻找您尚未定位的最小元素。我不知道这是否是个问题，但我不确定您是否意识到这一点。也就是说，我认为这可能是一件好事，因为在大多数情况下冒泡排序的效率低于选择排序(除非列表已经接近排序)。

希望这对您有所帮助!