我正在使用合并排序功能。我没有整理-我正在尝试完成我的合并部分。假设我正在学习C++,对指针有粗略的了解,并且不了解std::vector::iterator的所有规则(就此而言,也不是std::vector的)。

假定num是原始std::vector的大小,该值已从大小为“int ar [num]”的数组中复制(std::copy)值。假设farray的值为(0到(num / 2)),sarray的值为((num / 2)到num)。

int num = original.size();
std::vector<int> final(num);

for (std::vector<int>::iterator it = farray.begin(); it != farray.end(); ++it) {
     for (std::vector<int>::iterator iter = sarray.begin(); iter != sarray.end(); ++iter) {
         if (*it > *iter) final.push_back(*it);
          else
               final.push_back(*iter);
     }
}

这段代码可以编译,而我最新的稳定版Bloodshed Dev-C++不会引发任何警告或错误。我不知道这是否有效,我仍然需要尝试找出final的所有值。我只想知道这是否是普遍现象,容易出错或只是样式不好。如果是的话,你会怎么做

最佳答案

这是有效的...但是for循环可能不是您想要的。当您使用两个for循环时,每次外部循环循环时,您的内部循环都会回到起始位置。因此,如果您的 vector 包含:

farray: 10 9 8 4 3
sarray: 7 6 4 3 1

然后,您的最终数组将包含以下内容:
10 10 10 10 10 9 9 9 9 9 8 8 8 8 8 7 6 4 4 4 7 6 4 3 3

因为您要测试每个组合,然后将较大的组合添加到最终列表中。更好的解决方案可能是记住每个列表的迭代器,并且只使用一个循环。与其遍历列表,不如遍历两个列表-如果sarray的数目更大,则增加sarray迭代器,并将其与旧的farray迭代器进行比较。当sarray和farray为空时,停止循环。
vector<int> fiter = farray.begin();
vector<int> siter = sarray.begin();
vector<int> final;

// Let's traverse both farray and sarray.
// We'll want to stop this loop once we've traversed both lists.
while (fiter != farray.end() && siter != sarray.end())
{
    if (fiter == farray.end())
    {
        // we must have gone right through farray -
        // so use the value from sarray, and go to the next one
        final.push_back(*siter);
        siter++;
    }
    else if (siter == sarray.end())
    {
        // we must have gone right through sarray -
        // so use the value from farray, and go to the next one
        final.push_back(*fiter);
        fiter++;
    }
    else if (*siter > *fiter)
    {
        // siter is the bigger of the two - add it to the final list, and
        // go to the next sarray entry
        final.push_back(*siter);
        siter++;
    }
    else // *fiter >= *siter
    {
        // fiter is the bigger of the two - add it to the final list, and
        // go to the next farray entry
        final.push_back(*fiter);
        fiter++;
    }
}

我还没有测试过-如果这是用于作业,那么请尝试了解自己所做的一切,自己去写,而不要复制粘贴。

10-05 20:23
查看更多