c - 队列排序功能

Question

我想对字符串队列进行排序。

我的武器库中只有以下功能:

queue.count() - returns size
queue.pop() - return head, delete head
queue.push(String str) - add string at head
queue.get(int index) - return value stored at index

queue object - original strings stored in here
temp object - sorted strings should go here
temp1 object - temporary queue for help with sorting

我已经像这样初始化了队列:

String a[] = {"First", "third", "second"};

  for (int i = 0; i < 3; i++)
    queue.push(a[i]);

我已经尝试并编写了这段代码:

 temp.push(queue.peek());

  for (int i = 0; i < queue.count(); i++)
  {
    for (int j = 0; j < temp.count(); j++)
    {
      if (temp.get(j) != queue.get(i))
      {
        if (temp.get(j) > queue.get(i))
        {
          temp.push(queue.get(i));
        }
        else
        {
          for (int k = 0; k < temp.count(); k++)
            temp1.push(temp.pop());

          temp.push(queue.get(i));

          for (int k = 0; k < temp1.count(); k++)
            temp.push(temp1.pop());
        }
      }
    }
  }

它应该返回:

第一

第二个

第三

但它返回:

第一

第二个

第三

第三

第二个

Answer 1

我假设这是创造性思维的练习，而不是现实世界的问题。尽管在磁带驱动器和内存有限的时代，类似的事情可能是一个现实问题。

如果您所能做的就是使用队列的 pop 和 push 方法，那么您可以执行本质上非常低效的冒泡排序。这需要 O(n^2) 次操作和 O(1) 额外空间。

伪代码:

size = queue.Count

for i = 0 to size-1
    largest = queue.pop()
    for j = 1 to size-1
        temp = queue.pop()
        if temp > largest
            queue.push(largest)
            largest = temp
        else
            queue.push(temp)
        end if
    end for
    queue.push(largest)
end for

因此，第一次循环时，它确保最大的项目位于队列的末尾。下一次，它将把第二大的放在原来的位置，依此类推。

可以进行一些小的优化，但它们不会对运行时间产生太大影响，因为您仍然必须每次通过循环弹出和推送每个项目。

可能存在提前退出的情况，就像冒泡排序一样。如果在内循环的每次迭代中，temp >largest，那么您就知道队列是有序的。这可能是一个有用的优化，而且实现起来并不难:

size = queue.Count
isInOrder = false
while isInOrder == false
    isInOrder = true
    largest = queue.pop()
    for j = 1 to size-1
        temp = queue.pop()
        if temp > largest
            queue.push(largest)
            largest = temp
        else
            queue.push(temp)
            isInOrder = false
        end if
    end for
    queue.push(largest)
end while

鉴于您还可以调用队列的 get 方法，因此可能有一种更快的方法来执行此操作。仍然是 O(n^2) 复杂度，但实际运行时间可能会更好。我得考虑一下。