我需要创建一个使用堆栈和队列对整数数组进行排序的方法。例如，如果给定 [-1, 7, 0, 3, -2] -> [-2, -1, 0, 3, 7]。我完全不知道如何做这个问题，因为我只会使用排序方法，但是对于这个问题，我不允许这样做。谁能解释如何使用堆栈和队列来做到这一点？
问问题
10619 次
4 回答
9
许多快速排序算法（例如合并排序和快速排序）可以有效地在链表上实现，方法是您可以有效地将单链表视为堆栈（通过在前面添加元素）或队列（通过将元素附加到背部）。因此，解决此问题的一种可能方法是采用其中一种排序算法并处理它，就好像您正在排序链表而不是正常序列一样。
例如，这是一种使用队列实现归并排序的简单方法。我已经将其编写为 sort 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 2 ) 时间内运行。对于一个有趣的练习，尝试让它随机选择枢轴以获得预期的 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 2 ) 而不是 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());
}
希望这可以帮助！
于 2013-06-21T20:03:30.140 回答
5
您可以使用堆栈和队列相当轻松地实现选择排序：
如果数据原本在栈上，则将其全部放入Queue，并执行以下操作：
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.
}
排序结束后，元素将在 Stack 上排序，删除它们将按从大到小的顺序返回数据（可以很容易地反转）。
不，这不是很有效，我假设这是一个家庭作业。实际上，如果你想对数据进行排序，你应该使用 Arrays.sort 或 Collections.sort 来实现对象的合并排序和基元的快速排序。这些将快得多（O（NlogN）与O（N * N））。但是要意识到，您需要在数组或列表中包含数据才能执行此操作，而不是堆栈或队列。
于 2013-06-21T19:49:40.407 回答
4
要简单地排序，array您可以使用Arrays.sort().
具体来说，对于队列，PriorityQueue您需要对Queue. 看看java 文档。
PriorityQueue您可以在using方法中插入值，add()您将得到一个排序Queue后的结果。您还可以使用Comparator.
于 2013-06-21T19:45:49.970 回答
1
堆栈和队列是数据结构。堆栈是 FILO，队列是 FIFO。如果您了解这些数据结构的工作原理，您将能够弄清楚这一点。最终，您可以使用通常用于此类问题的相同逻辑，除了您需要使用堆栈和队列作为数据结构。
在 Java 中使用堆栈的一种方法是使用递归方法对数字进行排序，因为 Java 有一个内部内存堆栈。
希望有帮助。
于 2013-06-21T19:46:24.643 回答