c - 按顺序合并(交错)两个排序的数组(但合并后不排序)

Question

我有一个元素数组 1 5 9(例如 a1 a2 a3)
第二个元素数组 2 4 8 (e.g. b1 b2 b3)

我希望输出为 1,2 5,4 9,8(即 a1,b1 a2,b2 a3,b3)...这可能吗？我尝试的所有循环都将整个事物排序为 1、2、4、5、8、9？

代码块:

void merge(int a[], int m, int b[], int n, int sorted[]) {
  int i, j, k;

  j = k = 0;

  for (i = 0; i < m + n;) {
     if (j < m && k < n) {
        if (a[j] < b[k]) {
          sorted[i] = a[j];
          j++;
        }
        else {
          sorted[i] = b[k];
          k++;
        }
        i++;
     }
     else if (j == m) {
        for (; i < m + n;) {
          sorted[i] = b[k];
          k++;
          i++;
        }
     }
     else {
        for (; i < m + n;) {
          sorted[i] = a[j];
          j++;
          i++;
        }
     }
  }
}

Answer 1

您的情况:

if (a[j] < b[k]) {

强制排序，但你说你不想排序，所以不要这样做。

我更喜欢更简单的循环结构:

while (j < m && k < n)
{
    sorted[i++] = a[j++];
    sorted[i++] = b[k++];
}
while (j < m)
    sorted[i++] = a[j++];
while (k < n)
    sorted[i++] = b[k++];

这更接近于惯用的 C。

问题中的要求不依赖于正在排序的输入数组——它只是按顺序交错两个数组的元素，直到一个或另一个用完数据，然后复制其余的(如果有的话)另一个数组输出。

可以简化此代码 — 它不需要 j 和 k:

int i = 0;
int j;
int min = (m < n) ? m : n;

for (j = 0; j < min; j++)
{
    sorted[i++] = a[j];
    sorted[i++] = b[j];
}
while (j < m)
    sorted[i++] = a[j++];
while (j < n)
    sorted[i++] = b[j++];

只有一个 while 循环会执行循环体，但是 while 条件使得单独的 if 测试变得多余。