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

原文 标签 java sorting linked-list

我正在用 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;
            }
        }
    }

最佳答案

我花了几分钟观察你的代码是否有错误,但没有发现。

我会说,直到有人更聪明或更努力工作出现之前,您应该尝试自己调试。如果您有像 Eclipse 这样的 IDE,您可以在查看变量值的同时单步执行代码;如果没有,您可以在几个地方插入打印语句,并根据您的预期手动检查您所看到的内容。

更新我

我复制了您的代码并对其进行了测试。除了它按降序排序(这可能不是您想要的)这一事实之外,它还可以完美地用于 0、1 和 10 个随机节点的样本。那么问题出在哪里呢?

更新二

仍在猜测“它没有对条目进行完全排序”的含义。您可能期望按字典排序(即 'B' 之前的 'a'),而对于混合大写/小写的单词,这并没有按计划出现。这种情况下的解决方案是使用 String方法 compareToIgnoreCase(String str) .

关于java - 在 Java 中手动排序链表(按词法),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1854870/

相关文章:

java - 具有运行时未知字段的定制Gson序列化器

java - 使用JDom2在Android上编写XML文件

java - 对来自同一类的不同实例的值进行排序

java - 优化Java模式匹配功能以不同的顺序打印,可能进行链表操作

java - 旋转后OnRestoreInstanceState返回null

ios - Swift:按字母顺序对数组进行排序

java - 如何在Java中实现多线程MergeSort

java - 如何将信息添加到对象类?

performance - 与链表反转相关的想法

java - 在另一个模态JFace对话框顶部打开模态JFace对话框