0

我需要遍历 a 和 b 数组，将 a 和 b 中的元素复制到组合中，以使组合最终被排序。

例如，如果 a 是 {3, 5, 7, 7, 9}，b 是 {2, 5, 8, 1234}（所以 combo 必须有 9 个元素），那么这个函数会将 combo 设置为 {2, 3, 5、5、7、7、8、9、1234}。我需要有效地做到这一点：当我将值放入组合中时，我需要将它们放在正确的位置；不要随意，稍后重新排列它们。

我在 while 循环中尝试了一个嵌套的 for 循环，但我得到了一些奇怪的结果。我似乎无法找到超越最低数字的方法。例如，一旦我将最小的数字添加到组合数组中，我就无法弄清楚如何丢弃它本身。谢谢您的帮助。

void merge( 
    unsigned combo[], 
    const unsigned a[],
    unsigned aElements,
    const unsigned b[],
    unsigned bElements 
){

    if (mySort(a, aElements) == 0) {
        cout << "The first array is not sorted";
        exit(1);
    }

    if (mySort(b, bElements) == 0) {
        cout << "The second array is not sorted";
        exit(1);
    }

    unsigned combinedElements;
    unsigned lowest = 0;
    unsigned i = 0;

    combinedElements = aElements + bElements;

    while (i < combinedElements) {
        for (int n = 0; n < combinedElements; n++) {
            if (a[i] < b[n]) {
                lowest = a[i];
            }

            else {
                lowest = b[n];
            }
        }

        combo[i] = lowest;
        i++;
        cout << combo[i] << endl;
    }


}
4

5 回答 5

4

除非这是家庭作业，否则请使用std::merge

void merge( 
    unsigned combo[], 
    const unsigned a[],
    unsigned aElements,
    const unsigned b[],
    unsigned bElements 
){
    std::merge(a, a+aElements, b, b+bElemnts, combo);
}

如果这是家庭作业，试试这个算法：

index_result = 0; index_a = 0; index_b = 0;
while(index_a < size_a && index_b < size_b)
  if(a[index_a] < b[index_b])
    result[index_result++] = a[index_a++]
  else
    result[index_result++] = b[index_b++]
while(index_a < size_a)
  result[index_result++] = a[index_a++]
whle(index_b < size_b)
  result[index_result++] = b[index_b++]
于 2013-02-14T23:24:22.533 回答
3

我假设这是某种类型的作业，如果不是，请使用std::merge.

如果要手动推出此功能，则需要考虑使用三个游标：两个是两个不同数组的输入游标，另一个是输出（写入）游标。

在决定要从哪个数组中移动下一个元素后，您需要复制和更新两个游标，即该数组中的读取游标（因为该元素已被消耗）和最终数组中的写入游标（因为位置已被写入）。

我希望这足以引导您找到解决方案:)

于 2013-02-14T23:27:53.410 回答
1

这是您可以尝试的标准内容列表：http ://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

另外，您是否考虑过类似的伪代码：

创建一个新数组[旧数组的大小减一] mempcy(新数组，开始到删除点-1) mempcy(新数组，删除点+1到结束)

从新数组排序

再次罚款最低的数字...

于 2013-02-14T23:26:04.163 回答
0

这是一个非常紧凑的解决方案，应该易于阅读和理解。

我假设combo有足够的空间来容纳结果并且a已经b订购（如您的示例所示）：

void merge(unsigned combo[], 
           const unsigned a[],
           unsigned aElements,
           const unsigned b[],
           unsigned bElements)
{
    while(aElements + bElements > 0)
    {
      if(bElements == 0 || (aElements > 0  && *a < *b))
      {
          aElements--;
          *combo++ = *a++;
      }
      else
      {
          bElements--;
          *combo++ = *b++;
      }
   }
}

它可以稍微调整以获得更好的性能，但它非常优雅和可读。另外，此代码同时兼容 C 和 C++。

于 2013-02-14T23:29:36.180 回答
0

假设这是用于家庭作业或类似的事情，并且您不允许使用标准的东西std::merge，例如 2 个排序列表的合并算法可以以线性复杂度完成，如下所示：

void merge( unsigned combo[], const unsigned a[], unsigned aElements, const unsigned 
b[],    unsigned bElements ){

    if (mySort(a, aElements) == 0) {
        cout << "The first array is not sorted";
        exit(1);
    }

    if (mySort(b, bElements) == 0) {
        cout << "The second array is not sorted";
        exit(1);
    }

    int i,j,k =0;
    while (i<aElements && j<bElements)
    {
        if (a[i]<=b[j])
        {
            combo[j++]=a[i++];
        } else
        {
            combo[j++]=b[j++];
        }
    }

    //add remaining elements. at least one of these loops will not happen
    while (i < aElements) combo[j++]=a[i++];
    while (j < bElements) combo[j++]=b[j++];
}
于 2013-02-14T23:35:33.357 回答