双向链表上的快速排序 [英] QuickSort on Doubly Linked List

问题描述

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

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


}

推荐答案

快速浏览一下，您的列表似乎不仅是双向链接的，而且在末端也是相连的(所以它更像是一个 Ring 而不是 like一个列表).换句话说，如果我要遍历您的列表(包含元素 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 extends 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

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