使用堆栈和队列对数组进行排序

Question

我需要创建一个方法,使用Stack和Queue对整数数组进行排序.例如,如果给定[-1,7,0,3,-2] - > [ - 2,-1,0,3,7].我完全迷失了如何处理这个问题,因为我只会使用排序方法,但是对于这个问题,我不允许这样做.任何人都可以解释如何使用堆栈和队列执行此操作？

Answer 1

通过使用以下事实可以有效地在链表上实现许多快速排序算法(例如mergesort和quicksort),即可以将单链表单作为堆栈(通过在前面添加元素)或队列(通过附加元素)背部).因此,解决此问题的一种可能方法是采用其中一种排序算法并对其进行处理,就好像您要对链接列表而不是正常序列进行排序一样.

例如,这是一种可以使用队列实现mergesort的简单方法.我已经写了这个来排序Integer,但这可以很容易地扩展到处理其他类型:

public void mergesort(Queue<Integer> sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Otherwise, split the sequence in half. */
    Queue<Integer> left  = new LinkedList<Integer>(),
                   right = new LinkedList<Integer>();
    while (!sequence.isEmpty()) {
        left.add(sequence.remove());
        if (!sequence.isEmpty()) {
           right.add(sequence.remove());
        }
    }

    /* Recursively sort both halves. */
    mergesort(left);
    mergesort(right);

    /* Merge them back together. */
    merge(left, right, sequence);
}

private void merge(Queue<Integer> one, Queue<Integer> two,
                   Queue<Integer> result) {
    /* Keep choosing the smaller element. */
    while (!one.isEmpty() && !two.isEmpty()) {
        if (one.peek() < two.peek()) {
            result.add(one.remove());
        } else {
            result.add(two.remove());
        }
    }

    /* Add all elements from the second queue to the result. */
    while (!one.isEmpty()) {
        result.add(one.remove());
    }
    while (!two.isEmpty()) {
        result.add(two.remove());
    }
}

总的来说,这将在O(n log n)时间内运行,这是渐近最优的.

或者,您可以使用quicksort,如下所示:

public void quicksort(Queue<Integer> sequence) {
    /* Base case: Any 0- or 1-element sequence is trivially sorted. */
    if (sequence.size() <= 1) return;

    /* Choose the first element as the pivot (causes O(n^2) worst-case behavior,
     * but for now should work out fine.  Then, split the list into three groups,
     * one of elements smaller than the pivot, one of elements equal to the
     * pivot, and one of elements greater than the pivot.
     */
    Queue<Integer> pivot = new LinkedList<Integer>(),
                   less  = new LinkedList<Integer>(),
                   more  = new LinkedList<Integer>();

    /* Place the pivot into its list. */
    pivot.add(sequence.remove());

    /* Distribute elements into the queues. */
    while (!sequence.isEmpty()) {
        Integer elem = sequence.remove();
        if      (elem < pivot.peek()) less.add(elem);
        else if (elem > pivot.peek()) more.add(elem);
        else                          pivot.add(elem);
    }

    /* Sort the less and greater groups. */
    quicksort(less);
    quicksort(more);

    /* Combine everything back together by writing out the smaller
     * elements, then the equal elements, then the greater elements.
     */
    while (!less.isEmpty())  result.add(less.remove());
    while (!pivot.isEmpty()) result.add(pivot.remove());
    while (!more.isEmpty())  result.add(more.remove());
}

这在最佳情况下运行O(n log n)时间和最坏情况O(n ²)时间.对于一个有趣的练习,尝试让它随机选择枢轴以获得预期的O(n log n)运行时.:-)

对于完全不同的方法,您可以考虑对值进行最不重要的数字基数排序,因为您知道它们都是整数:

public void radixSort(Queue<Integer> sequence) {
    /* Make queues for values with a 0 in the current position and values with a
     * 1 in the current position.  It's an optimization to put these out here;
     * they honestly could be declared inside the loop below.
     */
    Queue<Integer> zero = new LinkedList<Integer>(),
                   one  = new LinkedList<Integer>();

    /* We're going to need 32 rounds of this, since there are 32 bits in each
     * integer.
     */
    for (int i = 0; i < 32; i++) {
        /* Distribute all elements from the input queue into the zero and one
         * queue based on their bits.
         */
        while (!sequence.isEmpty()) {
            Integer curr = sequence.remove();

            /* Determine whether the current bit of the number is 0 or 1 and
             * place the element into the appropriate queue.
             */
            if ((curr >>> i) % 2 == 0) {
                zero.add(curr);
            } else {
                one.add(curr);
            }
        }

        /* Combine the elements from the queues back together.  As a quick
         * note - if this is the 31st bit, we want to put back the 1 elements
         * BEFORE the 0 elements, since the sign bit is reversed.
         */
        if (i == 31) {
            Queue<Integer> temp = zero;
            zero = one;
            one = temp;
        }
        while (!zero.isEmpty()) result.add(zero.remove());
        while (!one.isEmpty())  result.add(one.remove());
    }
}

这将在时间O(n log U)中运行,其中U是可以存储在a中的最大可能值int.

当然,所有这些算法都是高效和优雅的.但有时候,你会想要做一些像bogosort这样缓慢而不优雅的事情.现在,bogosort有点难以实现,因为它通常需要您对输入序列进行洗牌,这对阵列更容易实现.但是,我们可以模拟对队列进行混洗,如下所示:

• 在队列中选择一个随机索引.
• 循环通过那么多元素.
• 从队列中删除该元素并将其添加到结果中.
• 重复.

这最终需要花费时间O(n ²)而不是O(n),这具有使bogosort花费预期时间O(n ²&mdot; n!)而不是O(n&mdot; n!)的不幸副作用.但是,这是我们必须付出的代价.

public void bogosort(Queue<Integer> sequence, Random r) {
    while (!isSorted(sequence)) {
        permute(sequence, r);
    }
}

/* Checking if a sequence is sorted is tricky because we have to destructively modify
 * the queue.  Our process will be to cycle the elements of the sequence making sure
 * that each element is greater than or equal to the previous element.
 *
 * Because we are using bogosort, it's totally fine for us to destructively modify
 * the queue as long as all elements that were in the original input queue end up
 * in the resulting queue.  We'll do this by cycling forward through the elements
 * and stopping if we find something mismatched.
 */
private void isSorted(Queue<Integer> sequence) {
    int last = Integer.MIN_VALUE;

    for (int i = 0; i < sequence.size(); i++) {
        int curr = sequence.remove();
        sequence.add(curr);

        if (curr < last) return false;
    }
    return true;
}

/* Randomly permutes the elements of the given queue. */
private void permute(Queue<Integer> sequence, Random r) {
    /* Buffer queue to hold the result. */
    Queue<Integer> result = new LinkedList<Integer>();

    /* Continuously pick a random element and add it. */
    while (!sequence.isEmpty()) {
        /* Choose a random index and cycle forward that many times. */
        int index = r.nextInt(sequence.size());
        for (int i = 0; i < index; i++) {
            sequence.add(sequence.remove());
        }
        /* Add the front element to the result. */
        result.add(sequence.remove());
    }

    /* Transfer the permutation back into the sequence. */
    while (!result.isEmpty()) sequence.add(result.remove());
}

希望这可以帮助!

Answer 2

您可以使用Stack和Queue轻松实现Selection排序:

如果数据最初位于堆栈中,请将其全部放在队列中,并执行以下操作:

int size = list.length; // list is the int[] sent as a method parameter.
while (size > 0) { // until we've placed all elements in their sorted positions
  int min = Integer.MAX_VALUE; // make sure the minimum is bigger than all the data
  for (int i = 0; i < size; i++) { // check all elements in the queue
    int temp = queue.dequeue(); // mark the current element
    if (temp < min) min = temp; // if it's a possible minimum record it.
    queue.enqueue(temp); // place it back in the queue so we don't lose data.
  }
  for (int i = 0; i < size; i++) { // go through and remove the minimum element
    int temp = queue.dequeue(); // mark the currently removed element
    if (temp == min) break; // if it's the minimum, stop we've removed it.
    queue.enqueue(temp); // otherwise put it back on.
  }
  stack.push(min); // put the minimum value on the stack (in sorted order)
  size--;  // we have one less element to consider, so decrement the size.
}

排序结束后,元素将在堆栈上排序,删除它们将返回数据按顺序最大(可以很容易地反转).

不,这不是很有效,我假设这是一个家庭作业.如果你想对数据进行排序,你应该使用Arrays.sort或Collections.sort来实现对象的合并排序和基元的快速排序.这些将更快(O(NlogN)对O(N*N)).但要意识到,您需要在数组或列表中包含数据才能执行此操作,而不是堆栈或队列.