如何使用链表进行选择排序

Question

我想我对选择排序有基本的想法，但由于某种原因它不起作用，我不知道为什么？有人知道这里有什么问题吗？

几点建议：

.getValue() 只返回节点中的对象，我使用的是整数。

Node tempNode = new Node(null,null,node.getValue())，第一个 null 用于上一个，第二个 null 用于下一个，第三个只是设置节点中的对象，在这种情况下为整数。

我的输入是：9 5 8 6 10 4

我的输出是这样的。由于某种原因，它一遍又一遍地设置 4：4 5 5 4 4 4

 public void SelectionSort()

  {

      Node<T> node2;

      Comparable temp;

      Node<T> Nodemin;

      for(Node<T> node = front;node != null; node = node.getNext())

      {

          Nodemin = node;

          for(node2 = node.getNext();node2 != null; node2 = node2.getNext())

          {

              temp = node.getValue();

              if(temp.compareTo(node2.getValue()) > 0)

              {

                  Nodemin.setValue(node2.getValue());

              } 

              Nodemin = Nodemin.getNext();

          }

          System.out.println(Nodemin.getValue());

          Node<T> tempNode = new Node(null,null,node.getValue());

          node.setValue(Nodemin.getValue());

          Nodemin.setValue(tempNode.getValue());

      }

  }

Answer 1

当您说Nodemin = Nodemin.getNext();时，您将要交换的项目（所选项目）指向超出最小值的位置。这有一个不需要的副作用，当您进行交换时，您在列表中稍后放置的数字将超出您正在交换的数字，我相信。但是在设置 Nodemin 的值时存在一个更微妙的缺陷，因为您一直在列表中查找较低的数字。因为 Nodemin 指向一个特定的位置，所以每次找到一个新的最低元素时，您不仅会更改 Nodemin 的值，还会更改列表中某个项目的值，因为它们指向同一个位置。我认为您可以通过将 Nodemin 更改为两个独立的东西来解决这两个问题，每个东西都可以满足您的需求。让 minValue 像你的温度一样，只跟踪 minValue。让 minLocation 始终指向 minValue 所在的位置（永远不要在其上执行下一行，只需将其重置为找到新最小值的位置）。然后，当在内部 for 循环之外进行交换时，在 minLocation 指向的位置进行交换，并使用值 minValue。那应该解决它。或者它也应该可以替换if(temp.compareTo(node2.getValue()) > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Nodemin.setValue(node2.getValue());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Nodemin = Nodemin.getNext();和if(temp.compareTo(node2.getValue()) > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Nodemin = node2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;跟踪和调试的建议是好的。你会看到我所说的证据，我相信，并发现我犯的任何错误。