java - 在 Java 中手动排序链表(词法)

Question

我正在用 Java 实现自己的链表。节点类只有一个名为“name”的字符串字段和一个名为“link”的节点。现在我有一个测试驱动程序类，它只按顺序插入几个名字。现在，我正在尝试编写一种排序方法来按字母顺序对节点进行排序，但遇到了一些麻烦。我从别人的帖子中找到了这个冒泡排序的伪代码并尝试实现它，但它没有完全对条目进行排序。我不太确定为什么。任何建议表示赞赏!

    private void sort()
    {
        //Enter loop only if there are elements in list
        boolean swapped = (head != null);

        // Only continue loop if a swap is made
        while (swapped)
        {
            swapped = false;

            // Maintain pointers
            Node curr = head;
            Node next = curr.link;
            Node prev = null;

            // Cannot swap last element with its next
            while (next != null)
            {
                // swap if items in wrong order
                if (curr.name.compareTo(next.name) < 0)
                {
                    // notify loop to do one more pass
                    swapped = true;

                    // swap elements (swapping head in special case
                    if (curr == head)
                    {
                        head = next;
                        Node temp = next.link;
                        next.link = curr;
                        curr.link = temp;
                        curr = head;
                    }
                    else
                    {
                        prev.link = curr.link;
                        curr.link = next.link;
                        next.link = curr;
                        curr = next;
                    }
                }

                // move to next element
                prev = curr;
                curr = curr.link;
                next = curr.link;
            }
        }
    }

Answer 1

我花了几分钟观察您的代码是否有错误，但一无所获。

我会说，在出现更聪明或更努力工作的人之前，您应该尝试自己调试它。如果你有像 Eclipse 这样的 IDE，你可以在观察变量值的同时单步执行代码；如果没有，您可以在几个地方插入打印语句，然后手动检查您看到的内容是否符合您的预期。

---

更新一

我复制了你的代码并测试了它。除了它按降序排序(这可能不是你想要的)之外，它对 0、1 和 10 个随机节点的样本非常有效。那么问题出在哪里呢？

更新二

仍在猜测“它没有完全对条目进行排序”是什么意思。您可能希望按字典顺序排序(即“B”之前的“a”)，但对于大小写混合的单词，这并没有按计划出现。这种情况下的解决方案是使用 String 方法 compareToIgnoreCase(String str)。