2

我想在同步双向链表上实现快速排序算法。我给函数“分区”左右边界，然后它开始在左侧搜索较低的值，并将较大的值放在右侧。这是有效的，因为我的枢轴元素始终是最右边的元素，并且在此步骤之后它位于中间。

我总是得到一个无限循环，我不知道为什么？也许错误的中止条件？

她我的代码：

private void quickSortRec(DoublyLinkedList in, ListElement l, ListElement r) {

    ListElement pivot = partition(in, l, r);



    if(pivot!=null && l!=r){
        quickSortRec(in, in.first, pivot.prev);
        quickSortRec(in, pivot.next, in.first.prev);
    }
}


public ListElement partition(DoublyLinkedList in, ListElement l, ListElement r){


    ListElement pivot = r;
    ListElement walker = l;


    if(l!=r){


        while(walker != pivot){

            if(walker.getKey() >= pivot.getKey()){

                System.out.println(walker.getKey());

                if(walker.prev == r){
                    l = walker.next;
                    r = walker;
                }
                else{


                    ListElement h1 = walker.prev;
                    ListElement h2 = walker.next;

                    h1.next = h2;
                    h2.prev = h1;
                    walker.prev = pivot;
                    walker.next = l;
                    pivot.next = walker;
                    l.prev = walker;
                    r = walker;

                }

            }
            walker = walker.next;
        }

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

        ListElement p = in.first;
        do{
            System.out.print(p.toString()+" ");
            p = p.next;
        }while(p != in.first);

        System.out.println();



        return pivot;

    }

    return null;
}


}
4

3 回答 3

1

快速浏览一下，您的列表似乎不仅是双向链接的，而且在末端也是连接的（所以它更像是一个环而不是一个列表）。换句话说，如果我要遍历您的列表（包含元素A, B, C, D），它不会是：

A -> B -> C -> D -> stop

相反，它会是

A -> B -> C -> D -> A -> B -> C -> D -> A -> B ..... etc.

我怀疑这可能是你有一个无限循环的原因。

我会在你的类中创建一个对你列表的最后一个元素的引用DoublyLinkedList（例如：）in.last，使用它来获取最后一个元素，并让第一个和最后一个元素链接到其中一个null或某种NullListElement extends ListElement

如果您必须将其保留为环，我仍会添加对列表最后一个元素的引用，以便您可以这样说：

if(walker == in.last) break; // stop
于 2013-04-30T15:07:36.430 回答
1 
Node partition(Node start, Node end){
    Node l = start;
    Node h = end.previous;
    Node pivot = end;

    if(end!=null && end.next!=start){ //Whenever deal with end.next, check null check
        while(h!=null && h.next!=l){//Whenever deal with end.next, check null check
            System.out.println("gumi");
            if(l.data<pivot.data)
                l=l.next;
            else if(h.data>pivot.data)
                h=h.previous;
            else{
                int temp = l.data;
                l.data = h.data;
                h.data = temp;
            }   
        }   
        int temp = pivot.data;
        pivot.data = l.data;
        l.data = temp;
    }
    return l;

}
void quicksort(Node start, Node end){
     System.out.println("jose");
   if(end!=null && end.next!=start ){ //Whenever deal with end.next, check null check , end should not be less than start: so the condition end.next!=start 
       System.out.println("Quixk");
       Node pivot = partition(start,end);
       quicksort(start, pivot.previous);
       quicksort(pivot.next, end);
   }

}
于 2017-03-13T06:32:56.320 回答
0

这是使用包含对第一个 ( )的引用的类的快速排序的实现，列表元素包含一个和和引用：DoublyLinkedListin.firstListElementkeyprevnext

public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {
    in.first = partition(in.first, in.first.prev);
    return in;
}

private ListElement partition(ListElement first, ListElement pivotElement) {
    ListElement left = first;
    ListElement right = pivotElement;

    while (left != pivotElement) {
        if (left.getKey() > pivotElement.getKey()) {
            ListElement next = left.next;
            if (left == first)
                first = next;
            //Remove currentLeft
            left.prev.next = left.next;
            left.next.prev = left.prev;

            //Connect with element after currentRight
            left.next = right.next;
            right.next.prev = left;

            //Connect with pivotElement
            left.prev = right;
            right.next = left;

            right = left; //Switch right with left, since we just swapped their positions
            left = next;  //Assign left to the next object (from the left part)
        } else {
            left = left.next;
        }
    }
    if (first != pivotElement.prev && first != pivotElement)
        first = partition(first, pivotElement.prev);
    if (pivotElement != right)
        partition(pivotElement.next, right);
    return first;
}

在撰写本文时，当我在使用最新 Haswel CPU 的台式计算机上运行此程序时，我得到以下结果：


快速排序： 1.000.000
项：696 毫秒 8.300.000 项：8131 毫秒

请注意，这比我对相同数据结构的MergeSort实现慢得多，为此我在具有相同输入的同一台计算机上获得以下时序：

合并排序：
1.000.000
项：466 毫秒 8.300.000 项：5144 毫秒

请注意，时间特定于我的硬件，您可能会得到不同的结果。

于 2014-01-10T20:36:52.777 回答