双链表上的QuickSort
我想在同步双链表上实现QuickSort算法。 我给左边框和右边框的function“分区”，然后它开始搜索左侧的较低值并将较大的值放在右侧。 这是有效的，因为我的枢轴元素总是最右边的，并且在这个步骤之后它位于中间。
我总是得到一个无尽的循环，我不知道为什么？ 也许错误的中止条件？
她的代码：
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 ），它将不是：
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
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.datapivot.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); } }
以下是使用DoublyLinkedList类的DoublyLinkedList实现，该类包含对第一个（ in.first ） ListElement的引用，list元素包含一个key以及prev和next引用：
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项目：696ms
8.300.000项目：8131ms
请注意，对于相同的数据结构，这比我的MergeSort实现要慢得多，为此我在具有相同输入的同一台计算机上获得以下时序：
归并：
1.000.000项目：466ms
8.300.000项目：5144ms
请注意，时间特定于我的硬件，您可能会得到不同的结果。