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

Question

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

Answer 1

许多快速排序算法(例如合并排序和快速排序)can be implemented efficiently on linked lists通过使用您可以有效地将单链表视为堆栈(通过将元素添加到前面)或队列(通过将元素添加到后面)这一事实。因此，解决此问题的一种可能方法是采用其中一种排序算法，并将其视为对链表而不是正常序列进行排序。

例如，这是您可以使用队列实现归并排序的一种简单方法。我写这个是为了对 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) 时间内运行，这是渐近最优的。

或者，您可以使用快速排序，如下所示:

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 是可以存储在 int 中的最大可能值。

当然，所有这些算法都是高效而优雅的。但是，有时您会想要进行缓慢且不优雅的排序，例如 bogosort .现在，bogosort 有点难以实现，因为它通常需要您打乱输入序列，这在数组上更容易做到。然而，我们可以模拟如下洗牌队列:

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

这最终花费的时间为 O(n²) 而不是 O(n)，这具有使 bogosort 花费预期时间 O(n^{2 &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());
}

希望这对您有所帮助!