1

我需要一种方法，我可以在二维数组中获取输入并以最快的方式对其进行逐行排序。我尝试同时使用 Input 和 Sort 它Insertion Sort。我使用的第二件事是我multimap单独取一行并插入键值作为我想要的值，映射值与该键相关作为一些虚拟值。由于地图在插入时对键进行排序，这可能是我认为的一种方式。

下面的代码用于确保我的 2D 中的 1 行的元素在 multimap 中排序。基本上你可以说我根本不想使用二维结构，因为我将一一单独使用这些行，因此可以被视为一维数组。我也希望他们在阅读 Input 时重新排列，所以我不需要额外的操作来做它们。 

for(long int j=1;j<=number_in_group;j++)
{
   cin >> arrival_time;
   arrival_map.insert(pair<long int, long int>(arrival_time,1));
}
4

1 回答 1

1

试试STL std::priority_queue？保证对输出进行排序，如果您将输入极化为二维对象（例如包含行号），那么您的队列将完美地构建。在这一点上，只需将队列中的数字分批“n”取出，其中“n”是您的行大小，每个都将被正确排序。您将需要一个元素类型，该元素类型对值和优先级队列中的行进行编码，并首先对行 # 进行排序，然后是值。您的示例long int用作您的值的数据类型。假设您的行不大于系统 unsigned int 的大小：

class Element
{
public:
   Element(unsigned int row, long int val)
      : myrow(row), myval(val)
   {};

   bool operator <(const Element& elem)
   {
      return (myrow < elem.myrow || 
             (myrow == elem.myrow && myval < elem.myvel);
   }

   unsigned int myrow;
   long int myval;
};


typedef std::priority_queue<Element> MyQueue;

注意：这利用了优先级队列的默认比较运算符 invoking std::less<>，它只是使用 item-defined 比较项目operator <()。一旦你有了这个，只需将你的矩阵推入队列，当你切换到下一行时增加行索引。

我的队列 MQ；

mq.push_back(Element(1,100));
mq.push_back(Element(1,99));
mq.push_back(Element(2,100));
mq.push_back(Element(2,101));

完成后弹出队列将导致以下序列：99 100 100 101

我希望这是你想要的。最后，请原谅语法错误和/或丢失的垃圾，因为我只是在飞行中炸毁了它并且没有编译器来检查它。一定要喜欢网吧。

于 2012-07-22T09:01:03.360 回答