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

Question

有人问我这个问题，我认为这是可行的，但是我很难想出一个算法来做到这一点。限制是您不能使用任何其他数据结构，也不能创建另一个队列。此外，您只能使用入队、出队和查看(不是优先级队列)。

感谢贡献:)

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 项，等等。因为算法将在最后堆叠这些最小值。

一旦我们找到最小值，我们需要再次遍历整个堆栈以抢夺它并将其堆叠在最后。

这里的主要思想是，同一元素的出队和入队将使我们能够遍历队列并在保持顺序的同时检查最小值/最大值。