链表的气泡排序算法

sorting java linked-list mergesort bubble-sort

2022-09-04 22:35:57

我编写了一个气泡排序算法来对链表进行排序。我是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 来获得更好的时间复杂性？

答案 1

有许多排序算法适用于链接列表，在这种情况下，mergesort可以很好地工作。我之前写了一个关于对链接列表进行排序的问题的回答，该问题探讨了链接列表上的许多经典排序算法，以及它们的时间和空间复杂性。您可以在链接列表上使用插入排序、选择排序、合并排序和快速排序。通过一些模糊，您还可以使堆排序工作。我的旧答案有关于如何做到这一点的细节。

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

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

希望这有帮助！

答案 2

如果您有一个可比较项的列表，则可以使用 Collections.sort 方法，该方法使用一种具有最坏情况时间复杂性的合并排序算法。无论如何，它比使用气泡排序更快。O(n log n)O(n²)

如果你想使用气泡排序算法，你可以这样做：

public static void bubbleSort(List<Integer> list) {
    boolean swapped;
    // repeat the passes through the list until
    // all the elements are in the correct order
    do {
        swapped = false;
        // pass through the list and
        // compare adjacent elements
        for (int i = 0; i < list.size() - 1; i++) {
            // if this element is greater than
            // the next one, then swap them
            if (list.get(i) > list.get(i + 1)) {
                Collections.swap(list, i, i + 1);
                swapped = true;
            }
        }
        // if there are no swapped elements at the
        // current pass, then this is the last pass
    } while (swapped);
}

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    Collections.addAll(list, 6, 1, 5, 8, 4, 3, 9, 2, 0, 7);
    bubbleSort(list);
    System.out.println(list); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}

^{另请参阅：
• 气泡排序输出不正确
• 使用分步输出 Java 8 进行气泡排序}