用堆栈和队列排序数组 [英] Sorting an array with Stacks and Queues
问题描述
我需要创建一个使用堆栈和队列排序整数数组的方法。例如，如果给出[-1,7，0,3，-2]→[-2，-1,0,3,7]。我完全失去了如何做这个问题，因为我只是使用排序方法，但是对于这个问题我不允许这样做。任何人都可以解释如何使用堆栈和队列来执行此操作？
I need to create a method which sorts an array of integers using a Stack and a Queue. For instance if given [-1, 7, 0, 3, -2] -> [-2, -1, 0, 3, 7]. I'm completely lost at how to do this question, because I would just use a sorting method, however for this question I am not allowed to do that. Can anyone explain how to do this with a Stack and a Queue?
推荐答案
许多快速排序算法（例如mergesort和quicksort） 可以通过链接列表高效实现，通过使用您可以有效地将单链接列表作为堆栈处理（由前置元素到前面）或队列（通过将元素附加到后面）。因此，解决这个问题的一种可能的办法是采用其中一种排序算法，并将其视为排序链表而不是正常序列。
Many fast sorting algorithms (for example mergesort and quicksort) can be implemented efficiently on linked lists by using the fact that you can efficiently treat a singly-linked list as a stack (by prepending elements to the front) or queue (by appending elements to the back). Consequently, one possible way to solve this problem would be to take one of those sorting algorithms and approach it as if you were sorting a linked list rather than a normal sequence.
例如，以下是使用队列实现mergeesort的一种简单方式。我写了这个，以排序整数，但这可以很容易地扩展到处理其他类型：
For example, here is one simple way that you could implement mergesort using queues. I've written this to sort Integers, but this could easily be extended to handle other types:
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 ）时间，这是渐近最优的。
Overall, this will run in O(n log n) time, which is asymptotically optimal.
或者，您可以使用quicksort，如下所示：
Alternatively, you could use quicksort, as shown here:
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 2 ）时间。对于一个有趣的练习，尝试随机选取该轴以获得预期的O（n log n）运行时间。 ： - ）
This runs in best-case O(n log n) time and worst-case O(n2) time. For an interesting exercise, try making it pick the pivot at random to get expected O(n log n) runtime. :-)
对于一个完全不同的方法，您可以考虑对值进行最低有效的数字基数排序，因为您知道它们都是整数： / p>
For an entirely different approach, you could consider doing a least-significant digit radix sort on the values, since you know that they're all integers:
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 中的最大可能值。
This will run in time O(n log U), where U is the maximum possible value that can be stored in an int.
当然，所有这些算法高效优雅。有时候，您会想要像 bogosort 一样缓慢而不雅的排序。现在，bogosort有些难以实现，因为它通常需要您随机播放输入序列，这对数组来说更容易做到。但是，我们可以模拟排队队列如下：
Of course, all of these algorithms are efficient and elegant. Sometimes, though, you will want to do a slow and inelegant sort like bogosort. Now, bogosort is somewhat difficult to implement, since it typically requires you to shuffle the input sequence, which is way easier to do on an array. However, we can simulate shuffling a queue as follows:
- 选择随机索引到队列中。
- 从队列中删除该元素并将其添加到结果中。
- 重复。
<
- Choose a random index into the queue.
- Cycle through that many elements.
- Remove that element from the queue and add it to the result.
- Repeat.
这样做最终会花费时间O（n 2 ）而不是O（n），这有不利的副作用使bogosort采取预期的时间O（n 2 &mdot; n！）而不是O（n&mdot; n！）。但是，这是我们必须支付的价格。
This ends up taking time O(n2) rather than O(n), which has the unfortunate side-effect of making bogosort take expected time O(n2 &mdot; n!) rather than O(n &mdot; n!). However, it's the price we have to pay.
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());
}
希望这有帮助！
这篇关于用堆栈和队列排序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
