JAVA - 按降序对链表进行排序

我试图编写一个排序链表的方法。这是对我的Java培训。JAVA - 按降序对链表进行排序

该方法应该得到一个带有值的链表，并用选择排序。 但不是通常的选择排序，而是选择排序，找到最大的数字，并将其放在链接列表的开始。直到列表排序。

我试着按照调试器，但是，我真的不明白我做错了什么。

这是我累了：

public IntList selectionSort() 
{ 
    IntNode tempMax = _head; 
    IntNode current = _head; 
    IntNode fromHere = null; 
    IntNode toHere = _head; 
    IntNode prev = null; 
    while(toHere != null) 
    { 
     current = toHere; 
     tempMax = toHere; 
     while (current != null) 
     { 
      if (current.getNext() != null && current.getNext().getValue() > tempMax.getValue()) 
       { 
        prev = current; 
        tempMax = current.getNext(); 
        current = current.getNext(); 
       } 
      else current = current.getNext();  
     } 
     prev.setNext(prev.getNext().getNext()); 
     tempMax.setNext(toHere);    
     if (fromHere == null) 
      _head = tempMax; 
     else fromHere.setNext(tempMax); 
     fromHere = tempMax; 
     toHere = fromHere.getNext(); 
    } 
    return this; 
}

enter image description here

来源

2012-02-07 Yuval Levy

为什么不移动'IntNode'内的值而不是移动'IntNode'。 – UmNyobe 2012-02-07 12:33:21

你可以在你的代码中加入一些注释吗？我很难跟踪哪些变量用于什么。 – 2012-02-07 13:01:00

一些提示：

如果你想最小的号码，然后current.getNext().getValue() > tempMax.getValue()应有的>代替<
您的代码也将当第一个元素是已经最小值失败，当你试图做一些事情来null
我能在这里过，current = current.getNext()看到重复的代码。指针操作通常很难编码，编写更清晰的代码坚持不重复自己的原则可能会帮助您查看错误！
它会帮助这里的人帮助你，如果你打印的编译器/运行时错误消息

来源

2012-02-07 12:09:51

我知道，但我想从大到小排序。 – 2012-02-07 12:13:52

这不是你在说明中说的 – UmNyobe 2012-02-07 12:19:53

错误...修正了它 – 2012-02-07 12:44:14

的主要问题与您的代码，就是当一个节点已经在它应该在的位置是胡作非为。如果我们执行：

5 -> 1 -> 2 -> 3-> 4

prev将是无效和我们崩溃。

如果我们做：

1 -> 4 -> 5 -> 3-> 2

在第一次迭代中，你获得

5 -> 4 -> 1 -> 3-> 2

到目前为止good.And那么，第二次迭代的循环之后

5 -> 4 -> 3-> 2// prev仍指着4,1消失

5 -> 4 -> 4。// tempMax = toHere所以tempMax-> tempMax，和其他元素都不见了

所以表现是prev在某种程度上是无效的。有一个快速修复，如toHere是最大的跳过重新定位，但快速修复不是你所需要的。您应该：

对某些特殊情况的反思。空列表，一个元素，列表已经排序，在倒车时，随机顺序，（重复的元素？）
写单元测试对每个案例
重写你的算法，并避免排序列表哦，是的，我忘了案例...。哑了它，你只需要在每一个给定的步骤中将第一个元素替换为在这一步中找到的最大值。
避免有冗余信息的变量。例如，tempMax应该始终是prev的下一个，因此仅有prev就足够了。否则，你正在花费脑细胞保持一致性。
再次测试套件的情况。

来源

2012-02-07 13:54:05 UmNyobe

JAVA - 按降序对链表进行排序

回答

相关问题