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

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)
          {
              Nodemin.setValue(node2.getValue());


          } 
          Nodemin = Nodemin.getNext();

与

if(temp.compareTo(node2.getValue()) > 0)
          {
              Nodemin = node2;


          } 

跟踪和调试的建议很好。我相信，您会看到我所说的证据，并发现我所犯的任何错误。