java - 对链表进行排序仅适用于冗余迭代器

Question

我编写了代码来对学校作业的 LinkedList 进行排序。它可以工作，但运行次数不够。所以我添加了第三个 for 循环，现在它可以工作了，但我不明白为什么它只适用于第三个迭代器。有人可以看看我的代码并告诉我我做错了什么吗？我应该怎么做？这感觉不对，几乎无法处理大于 1000 的链表。

    public void sort() {
    Node min;
    for (Node shouldNotNeedThis = head; shouldNotNeedThis != null; shouldNotNeedThis = shouldNotNeedThis.next) {
        for (Node ix = shouldNotNeedThis.next; ix != null; ix = ix.next) {
            min = ix;
            for (Node tx = ix.next; tx != null; tx = tx.next) {
                if (tx.compareTo(min) == -1) {
                    min = tx;
                }
            }
            if (min != ix) {
                swapNodes(ix, min);
                ix = min;
            }
        }
    }
}

public void swapNodes(Node currentNode, Node nextNode) {
    Integer temp = currentNode.data;
    currentNode.data = nextNode.data;
    nextNode.data = temp;
}

Answer 1

您的问题在这里:

        if (min != ix) {
            swapNodes(ix, min);
            ix = min;
        }

只需交换节点就足够了。通过将 ix 设置为 min，您可以将其设置为列表其余部分中间某个任意值，该值曾经保持最小值(但不再是了)。不幸的是， ix 是您用来迭代列表的变量。因此，每次设置 ix 时，您都会跳过一些元素。