0

我正在做我的快速排序练习，它使用 LinkedList 进行排序，（我知道它效率不高而且真的毫无意义，它是为了上课）。我了解快速排序方法的工作原理，以及三种策略的中位数。例如，我的代码仅在某些长度上正常工作。

这工作正常：

7 6 5 4 3 2 1, 枢轴 = 4

7 6 5, 枢轴 = 6 | 3 2 1, 枢轴 = 2

现在，对于任何不是那样的东西，即。

5 4 3 2 1, 枢轴 = 3

5 4, 抛出错误 | 2 1引发错误。

这是我拥有的代码：

在 LinkedList 中查找中间节点。

public Node findMiddleNode() {
    Node node1 = first;
    Node node2 = first;
    while(node2.getNext() != null && node2.getNext().getNext()!= null) {
        node1 = node1.getNext();
        node2 = node2.getNext().getNext();
    }
    return node1;
}

查找第一个、中间和最后一个节点的中值。

public Node medianOfThree() {
    Node firstNode = first;
    Node lastNode = last;
    Node middleNode = findMiddleNode();

    if((firstNode.getData() - middleNode.getData()) * (lastNode.getData() - firstNode.getData()) >= 0) {
        return firstNode;
    } else if((middleNode.getData() - firstNode.getData()) * (lastNode.getData() - middleNode.getData()) >= 0) {
        return middleNode;
    } else {
        return lastNode;
    }
}

从列表中删除枢轴，这是中断的方法。

private Node chooseAndRemovePivot() {
    Node pivot = medianOfThree();
    Node previous = first;

    // If the pivot is the first Node.
    if(previous == pivot) {
        first = previous.getNext();
    }

    // Gets the last Node before the pivot
    while(previous.getNext() != pivot) {
        previous = previous.getNext();
    }

    previous.setNext(pivot.getNext());
    pivot.setNext(null);
    size--;
    if (size == 0)
        last = null;
    return pivot;
}

谁能指出这里出了什么问题，我敢肯定这是我犯的一个简单错误。

编辑：解决方案；

在方法中chooseAndRemovePivot();

// If the pivot is the first Node.
if(previous == pivot) {
    first = previous.getNext();
} else {
    // Gets the last Node before the pivot
    while(previous.getNext() != pivot) {
        previous = previous.getNext();
    }
}

这使它适用于所有长度。

4

2 回答 2

2

该medianOfThree函数将返回pivot == first长度为 2 的列表。因此，此代码：

// Gets the last Node before the pivot
while(previous.getNext() != pivot) {
    previous = previous.getNext();
}

...永远不会找到终止条件，而是previous = null在到达列表末尾时分配。然后下一次迭代将抛出一个NullPointerException.

于 2013-06-11T21:16:16.750 回答
0

我相信错误出在您的 findMiddleNode() 函数中。具体来说， node2.getNext.getNext() 永远不会检查 node2.getNext() 是否为空

在具有偶数个项目的列表中， node2.getNext().getNext() 将运行到最后。有效地将语句减少为 Null.getNext() 这是一个错误。

例如使用列表

first -> a -> b -> null
  1. 第一个 node1 和 node2 设置为“first.
  2. 然后node1变成a，node2变成b。
  3. 然后 node1 变成 b 并且 node2 变成 b.getNext().getNext() 或者换句话说 Null.getNext。

该算法适用于奇数长度列表，因为 node2.getNext().getNext() 将始终落在 null

于 2013-06-11T21:23:52.210 回答