0

我正在尝试实现一个快速排序来对循环链接列表进行排序！

有一个DoublyLinkedList包含ListElements.

有ListElement元素优先，它引用了它的前任和继任者。

例如DoubleLinkyedListin 包含第ListElement一个。First 可以通过 first.prev 或 first.next 引用。

链表中的最后一个元素引用了第一个元素，例如last = first.prev；

我的问题是，我不断收到错误，但我不知道究竟是哪一个，因为它就像一个永无止境的循环，终端没有打印精确的异常。

我实现排序操作的类 Sorter.java 的代码：

package ads1ss13.pa;


public class Sorter {

public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {


    System.out.println("STARTE sort() in quicksorT()");

    in = Sort(in, in.first.getId(), in.first.prev.getId());

    return in;
}

public DoublyLinkedList Sort(DoublyLinkedList in, int l, int r)
{
    System.out.println("Sort()");

    l = in.first.getId();
    r = in.first.prev.getId();
    ListElement pivot = null;

    System.out.println("l: "+l+"; r: "+r);

    if(l < r)
    {
        pivot = in.first.prev;
    }

    System.out.println("pivot: "+pivot);

    System.out.println("Ausfuehren der Partition mit l, r, pivot");

    int p = Partition(in, l, r, pivot);

    System.out.println("Ausgabe aus Partition p: "+p);

    System.out.println("Ausführen der Sort() mit l und p-1 für r");


    Sort(in, l, p-1);

    System.out.println("Ausführen der Sort() mit p+1 für l, und r");
    Sort(in, p+1, r);

    return in;
}

public int Partition(DoublyLinkedList in, int l, int r, ListElement pivot)
{
    System.out.println("Partition()");

    int i = l;
    int j = r;
    ListElement r_ListElement = in.first.prev;
    ListElement i_element = in.first.next;
    ListElement j_element = pivot;

    System.out.println("i: "+i+"; j: "+j+", pivot: "+j_element);

    do {

        do {
            i = i + 1;
            i_element = i_element.next;
        } while (i_element.getKey() < pivot.getKey());

        do {
            j = j - 1;
            j_element = j_element.prev; 
        } while (j > i || j_element.getKey() > pivot.getKey());

        if(i_element.getKey() < j_element.getKey())
        {
            swap(in, i_element, j_element);
        }

    } while (i < j);

    swap(in, i_element, r_ListElement);

    return i;
}

public void swap(DoublyLinkedList in, ListElement links, ListElement rechts)
{
    if(links.next.getId()==rechts.getId()){

        ListElement Lprev = links.prev;
        ListElement Rnext = rechts.next;
        Lprev.next=rechts;
        rechts.prev=Lprev;
        links.next=Rnext;
        Rnext.prev=links;
        links.prev=rechts;
        rechts.next=links;

        }

        else if(rechts.next.getId()==links.getId())
        {
            swap(in, rechts, links);
        }
        else
        {
            ListElement Lprev=links.prev;
            ListElement Lnext = links.next; 
            links.next=rechts.next;
            links.prev=rechts.prev;
            rechts.next=Lnext;
            rechts.prev=Lprev; 
            links.prev.next=links;
            links.next.prev=links;
            rechts.prev.next=rechts;
            rechts.next.prev=rechts;
        }


        if(in.first.getId()==links.getId())
        {
            in.first = rechts;
        }
        else if(in.first.getId()==rechts.getId())
        {
            in.first = links;

        }
}
}

你知道为什么我的代码永远不会切换到第二个递归调用sort()以及返回哪个错误吗？

4

1 回答 1

0

这很难分析，因为我无法将代码放入调试器中。但是，有几件事可以让您走上正轨：

问题 1。

您将int landint r作为参数，但您立即覆盖它们：

l = in.first.getId();
r = in.first.prev.getId();

这几乎肯定不是您想要做的，因为您将一遍又一遍地重新启动。这可能是导致您无限循环的原因。

问题 2。

if(l < r)
{
    pivot = in.first.prev;
}

如果l >= r，枢轴是null，这将导致NullPointerException

问题 3。

您的分区逻辑错误。您不需要嵌套循环。一旦您将元素与枢轴进行比较，您就可以立即进行交换（您将始终知道它应该在枢轴的哪一侧）。

于 2013-05-08T14:18:37.057 回答