c - 如何合并不同大小的已排序序列？

Question

我正在寻找一种算法来将多个排序序列(比如说 X 个排序序列)合并到 c 中的一个排序序列中，您能提供一些示例吗？

请注意，每个序列都有不同的大小。

我想到了这一点，但序列可能有重叠的间隔。所以它不会工作。

x=s1[first] 
y=s2[last]
if(x<y) then put s1 after s2 in the output.
...

注意:我不想使用任何库

Answer 1

您可以像 N 路 merge sort 一样合并输入序列确实如此。

基本上，您检查每个有序输入序列的头部，并将最小头部附加到新的有序序列中(并更新您使用的序列的头部)。这样做直到所有输入序列都为空。

如果您有大量的输入序列需要合并，那么您可能需要维护输入序列头部的最小堆，而不是每次都对最小头部进行线性扫描。

#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct
{
  size_t size;
  int   *seq;

} Sequence;

Sequence *mergeSortedSequences(const Sequence *seqs[], size_t num_seqs)
{
  Sequence *ret = malloc(sizeof(Sequence));
  size_t    indexes[num_seqs];  /* NOTE: not valid C89; in C89 need to malloc instead or have seqs be non-const and trash the Sequences themselves */
  size_t    tot_size;
  size_t    i;

  if (NULL == ret)
    goto FAIL;

  ret->size = 0;

  /* calculate total size of merged Sequence, init indexes and cull any empty sequences from seqs */

  for (i = 0, tot_size = 0; i < num_seqs;)
  {
    if (0 != seqs[i]->size)
    {
      tot_size += seqs[i]->size;
      indexes[i] = 0;
      ++i;
    }
    else
    {
      seqs[i] = seqs[--num_seqs];  /* cull empty seq from seqs */
      printf("Swapping original seq %lu into position %lu\n", num_seqs, i);
    }
  }

  printf("Return sequence size is %lu; number of non-empty sequences: %lu\n", tot_size, num_seqs);

  ret->seq = calloc(tot_size + 1, sizeof(int));  /* NOTE: +1 so we don't ever calloc(0) */

  if (NULL == ret->seq)
    goto FAIL_RET;

  /* loop while non-empty sequences left */

  while (num_seqs)
  {
    /* find minimum of remaining seqs */

    int    min     = seqs[0]->seq[indexes[0]];
    size_t min_seq = 0;

    for (i = 1; i < num_seqs; ++i)
    {
      if (seqs[i]->seq[indexes[i]] < min)
      {
        min     = seqs[i]->seq[indexes[i]];
        min_seq = i;
      }
    }

    /* update ret */

    ret->seq[ret->size++] = min;

    printf("minimum value was from head of seq %lu; ret[%lu] = %d\n", min_seq, ret->size, min);

    /* update indexes, min_seq and seqs */

    ++indexes[min_seq];  /* "consume" the head of min_seq */

    if (indexes[min_seq] == seqs[min_seq]->size)  /* we've exhausted min_seq */
    {
      seqs[min_seq]    = seqs[--num_seqs];        /* cull empty sequence */
      indexes[min_seq] = indexes[num_seqs];
      printf("Swapping seq %lu into position %lu (2)\n", num_seqs, min_seq);
    }
  }

  printf("Success ret->size = %lu\n", ret->size);

  assert(NULL != ret && ret->size == tot_size);
  goto END;

  /* error handling and return */

FAIL_RET:
  free(ret);
  ret = NULL;

FAIL:
  assert(NULL == ret);

END:
  return ret;  
}

int main(int argc, char **argv)
{
  int       arr1[] = { -44, 0, 22, 49, 58, 101 };
  int       arr3[] = { -101, 14, 22, 31, 151 };
  int       arr4[] = { -1, 0, 1, 50, 200 };
  Sequence  seq0   = { 0, NULL };
  Sequence  seq1   = { sizeof(arr1) / sizeof(arr1[0]) };
  Sequence  seq2   = { 0, NULL };
  Sequence  seq3   = { sizeof(arr3) / sizeof(arr3[0]) };
  Sequence  seq4   = { sizeof(arr4) / sizeof(arr4[0]) };
  Sequence  seq5   = { 0, NULL };
  Sequence *seqs[6];
  Sequence *ret;
  size_t    i;

  seq1.seq = arr1;
  seq3.seq = arr3;
  seq4.seq = arr4;

  seqs[0] = &seq0;
  seqs[1] = &seq1;
  seqs[2] = &seq2;
  seqs[3] = &seq3;
  seqs[4] = &seq4;
  seqs[5] = &seq5;

  ret = mergeSortedSequences((const Sequence**) seqs, sizeof(seqs) / sizeof(seqs[0]));

  if (NULL == ret)
  {
    perror("Allocation failure!");
    abort();
  }

  printf("Merged sequence contains %lu elements:\n", ret->size);

  for (i = 0; i < ret->size; ++i)
    printf("\t%d\n", ret->seq[i]);

  return 0;
}