使用相同队列对队列进行排序

Question

我被问到这个问题,我认为这是可行的,但是我很难想出一个算法来做到这一点.限制是您不能使用任何其他数据结构,也不能创建另一个队列.此外,您只能使用enqueue,dequeue和peek(不是优先级队列).

Thanx为贡献:)

Answer 1

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)

升序排序,在O(n ^ 2)时间内,在空间O(1)中运行(即队列为O(n)空间,算法所需的额外空间为O(1))

说明:

本质上,我们遍历队列n次,每次迭代花费2n.

在每次迭代中,我们遍历整个队列并在相关项目数内选择最小值.因此,首先相关的项目数是n,因为我们希望它们中的最小值.下一次迭代我们想要最少的前n-1项,然后是n-2项等.因为算法将在最后堆叠这些最小值.

一旦我们找到最小值,我们需要再次迭代整个堆栈以便抓取它并将其堆叠在最后.

这里的主要思想是,一个队列后面的队列将允许我们迭代队列并检查最小/最大值,同时保留顺序.