java - 快速排序三中位数

Question

我正在做我的快速排序练习，它使用 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();
    }
}

这使其适用于所有长度。

Answer 1

对于长度为 2 的列表，medianOfThree 函数将返回 pivot == first。因此这段代码:

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

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