java - 双向链表上的快速排序

Question

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

我总是陷入无限循环，我不知道为什么？也许中止条件错误？

她的我的代码:

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;
}


}

Answer 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