排序使用同一队列队列 [英] Sorting a queue using same queue

问题描述

我一直在问这个问题，我认为这是可行的，但我有一个很难拿出有一个算法来做到这一点。这些限制是你不能使用任何其他数据结构，也没有创造另一个队列。你也只能用入队，出队和peek（不是一个优先级队列）。

感谢名单的贡献：）

解决方案

 排序（Q，N）：

  对于i = 0至n-1
    分= findMin（Q，N-I，N）
    重新排序（Q，分，N）
  结束了

findMin（Q，K，N）：

  分=无穷大

  对于i = 1到n
    CURR =出列（Q）的
    如果CURR＆LT;分和放大器;＆安培; I＆LT; = K
      分= CURR
    如果结束
    入队（Q，CURR）
  结束了

  返回分钟

重新排序（Q，分，N）：

  对于i = 1到n
    CURR =出列（Q）的
    如果（CURR！=分钟）//我假设有一种方法的任何两个项目之间的区别，这是不是难以执行
      入队（Q，CURR）
    如果结束
  结束了

  入队（Q，分）
 

升序排序，为O（N ^ 2）时间，空间O（1）（即队列为O（n）的空间，并通过算法所需的额外空间为O（1））

说明：

从本质上讲，我们通过队列n次，每次重复迭代成本2N。

在每次迭代中，我们经历了整个队列，并挑选物品的相关数量内的最小值。因此，在第一项的相关数为n，因为我们希望最小这一切。下一次迭代，我们需要的最小的第一n 1项，然后正 - 2项，等等。由于该算法将在结束堆叠这些最低

一旦我们找到的最小，我们需要再次遍历整个堆栈，以抢夺和堆栈它的结束。

这里的主要思想，是一个出列其次是同一元素的入队将使我们能够遍历队列，并检查最小/最大，而preserving订单。

I have been asked this question and I think it's doable, However I am having a hard time coming up with an algorithm to do this. The restrictions is that you can not use any other data structure nor create another queue. Also you only can use enqueue, dequeue and peek (NOT a priority queue).

Thanx for contributing :)

解决方案

Sort(Q,n):

  for i = 0 to n-1
    min = findMin(Q, n-i, n)
    reorder(Q, min, n)
  end for

findMin(Q, k, n):

  min = infinity

  for i = 1 to n
    curr = dequeue(Q)
    if curr < min && i<=k
      min = curr
    end if
    enqueue(Q,curr)
  end for

  return min

reorder(Q, min, n):

  for i = 1 to n
    curr = dequeue(Q)
    if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce
      enqueue(Q, curr)
    end if
  end for

  enqueue(Q,min)

Ascending sort, runs in O(n^2) time, in space O(1) (i.e. the queue is O(n) space, and extra space required by the algorithm is O(1))

Explanation:

Essentially, we iterate through the queue n times, each time the iteration costs 2n.

On each iteration, we go through the entire queue and pick the minimum within the relevant number of items. So at first the relevant number of items is n, since we want the minimum of them all. The next iteration we want the minimum of the first n-1 items, and then n-2 items, etc. Since the algorithm will stack these minimums at the end.

Once we found the minimum, we need to iterate over the whole stack again in order to snatch it and stack it on the end.

The main idea here, is that a dequeue followed by an enqueue of that same element will allow us to iterate over the queue and check minimum/maximum while preserving order.

这篇关于排序使用同一队列队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！