双链表上的QuickSort [英] QuickSort on Doubly Linked List

问题描述

我想在同步双链表上实现QuickSort算法。
我给函数 partition的左边界和右边界，然后它开始在左侧搜索较低的值，然后在右侧搜索较大的值。之所以有效，是因为我的枢轴元素始终是最右侧的元素，并且在此步骤之后它位于中间。

I want to implement the QuickSort Algorithm on a sync Doubly Linked List. I give the function "partition" the left and right border, then it starts to search lower values on the left side and put the greater ones on the right side. This works because my pivot Element is alway the most rightern one and after this steps it is in the middle.

我总是会遇到无尽的循环，我不知道为什么吗？

I always get an endless loop and I dont know why? Maybe wrong abort condition?

她的代码：

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


}

推荐答案

只是快速浏览一下，看来您的列表不仅是双重链接的，而且在两端都连接在一起（因此，它更像是环而不是列表）。换句话说，如果我要遍历您的列表（包含元素 A，B，C，D ），则不会是：

Just from a quick skim, it seems that your list is not only doubly linked, but also is connected at the ends (so it's more like a Ring than like a list). In other words, if I were to iterate over your list (containing elements A, B, C, D), it wouldn't be:

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

取而代之的是

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

我怀疑这可能就是您陷入无限循环的原因。

I suspect that could be why you are having an infinite loop.

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

I would create a reference to the last element of your list in your DoublyLinkedList class (example: in.last), use that for getting the last element, and have the first and last elements link to either null or some sort of NullListElement extends ListElement

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

If you must keep it as a ring, I will still add a reference to the last element of your list, so that you can say something like:

if(walker == in.last) break; // stop

这篇关于双链表上的QuickSort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！