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

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;

          } 

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