双端队列（Deque）快速排序

Question

我已经为我的快速排序功能苦苦思索了一段时间，但仍然不知道我做错了什么。

当我运行对包含随机生成的元素的双端队列进行快速排序时 [6,92,63,90,79,94,8,13,72,28]

结果为[13,8,28,94,92,63,72,90,79,6]

public class DoublyLinkedDeque<E extends Comparable<E>> implements DequeADT<E>
{
    ...

    public void quickSort(DoublyLinkedDeque<E> deque, Comparator<E> comp) 
    {
        int n = deque.size();
        if (n < 2) 
        {
            return;
        }
        // using first as arbitrary pivot
        E pivot = deque.first();                     
        DoublyLinkedDeque<E> left = new DoublyLinkedDeque<>();
        DoublyLinkedDeque<E> equalsPivot = new DoublyLinkedDeque<>();
        DoublyLinkedDeque<E> right = new DoublyLinkedDeque<>();
        while (!deque.isEmpty()) 
        {
            // divide original into left, equalsPivot, and right
            E element = deque.dequeueFront();
            int tmpCompare = comp.compare(element, pivot);
            // element is less than pivot
            if (tmpCompare < 0)                             
            {
                left.enqueueFront(element);
            }
            // element is equal to pivot
            else if (tmpCompare == 0)                       
            {
                equalsPivot.enqueueFront(element);
            }
            // element is greater than pivot
            else                                   
            {
                right.enqueueFront(element);
            }
        }
        // sort elements less than pivot
        quickSort(left, comp);                      
        // sort elements greater than pivot
        quickSort(right, comp);                      
        // concatenate results
        while (!left.isEmpty())
        {
            deque.enqueueFront(left.dequeueFront());
        }
        while (!equalsPivot.isEmpty())
        {
            deque.enqueueFront(equalsPivot.dequeueFront());
        }
        while (!right.isEmpty())
        {
            deque.enqueueFront(right.dequeueFront());
        }
    }
}


public static void main(String[] args)
{        

    DoublyLinkedDeque<Integer> deque = new DoublyLinkedDeque<Integer>();

    /* ADDING RANDOM NUMBER TO deque */

    Comparator<Integer> intComparator = new Comparator<Integer>()
    {
        @Override
        public int compare(Integer i1, Integer i2)
        {
            return (i1 < i2 ? -1 : i1 > i2 ? +1 : 0);
        }
    };

    deque.quickSort(deque, intComparator);

}

Answer 1

如果我对你的代码的理解是正确的，那么错误就在你连接结果的最后部分。

你从左边的部分开始（数字小于主元），移除它的第一个元素并将它从左边推入队列，所以它成为最右边的元素。然后你推枢轴，然后是右边部分的元素（比枢轴大的数字），成为队列中最左边的元素。

例如

左：[3]
枢轴：[5]
右：[7]

现在连接（按步骤）

左 -> 双端队列 [3]
pivot (enqueueFront) -> 双端队列 [5,3]
right (enqueueFront) -> deque [7,5,3]

所以让我们假设这个集合现在是左侧部分处理的结果。现在，如果您将该集合与 [9,8]

的另一组排序错误的较大值（右侧部分）组合

左：[7,5,3]
右：[9,8]

你得到（简化的步骤）

[7]
[5,7]
[3,5,7]
[9,3,5,7]
[8,9,3,5,7]

可以看出，部分排序的子列表的顺序随着每次递归而交替。导致包含部分排序片段的错误排序结果集。

TL;DR 检查连接的顺序或使用正确的添加操作（前面 vs 后面）

双端队列（Deque）快速排序

Double ended Queue (Deque) Quicksort

java

queue

quicksort