c - 如何在不使用排序算法的情况下将两个已排序的数组合并到第三个数组中？

Question

假设和限制:

• 有两个按升序排列的数组a[]和b[]，大小不同。

• 您必须按升序将它们合并到第三个数组 c[] 中。

• 您不能通过将两个数组复制到第三个数组来合并它们，然后应用排序算法对它们进行排序。

• 您不必在整个任务中使用任何排序算法。

• 您应该利用 a[] 和 b[] 已经排序的数组这一事实，它们可以合并，而无需对第三个数组 c[] 进行排序

  建议:

• 如果能添加注释行以方便初学者理解就太好了

• 最好使用的编码语言应该是C。(我也可以使用C++和Java)

• 我不会在这里提出或回答问题，因此请通过纠正或改进我的语言来帮助我更加清晰。

Answer 1

我猜你找到了这个例子 here (请引用链接!)，但这有点复杂。我更喜欢以下内容:

// c[] MUST be pre-allocated to at least n_a+n_b
void merge_sorted(int n_a, const int a[], int n_b, const int b[], int c[])
{
    int i = 0, j = 0, k = 0;
    while (i < n_a && j < n_b)
        if (a[i] < b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    while (i < n_a) c[k++] = a[i++];
    while (j < n_b) c[k++] = b[j++];
}

不过，它不会检查输入是否已排序。

编辑:函数内具有堆分配的版本:

// the caller is responsible for calling free() on the returned pointer
int *merge_sorted(int n_a, const int a[], int n_b, const int b[])
{
    int i = 0, j = 0, k = 0, *c;
    c = (int*)malloc((n_a + n_b) * sizeof(int));
    while (i < n_a && j < n_b)
        c[k++] = a[i] < b[j]? a[i++] : b[j++];
    while (i < n_a) c[k++] = a[i++];
    while (j < n_b) c[k++] = b[j++];
    return c;
}

我通常更喜欢让调用者管理堆分配。