Question

我正在撰写一份简单的合并功能,以根据一项指定职能(<>):

void merge(int left, int mid, int right, int(*compar)(const void *, const void *))
{
  // sublist sizes
  int left_size = mid - left + 1;
  int right_size = right - mid;

  // counts
  int i, j, k;

  // create left and right arrays
  B *left_list = (B*) malloc(left_size*sizeof(B));
  B *right_list = (B*) malloc(right_size*sizeof(B));

  // copy sublists, could be done with memcpy()?
  for (i = 0; i < left_size; i++)
    left_list[i] = list[left + i];

  for (j = 0; j < right_size; j++)
    right_list[j] = list[mid + j + 1];

  // reset counts
  i = 0; j = 0;

  for (k = left; k <= right; k++)
  {
    if (j == right_size)
      list[k] = left_list[i++];
    else if (i == left_size)
      list[k] = right_list[j++];
    // here we call the given comparision function
    else if (compar(&left_list[i], &right_list[j]) < 0)
      list[k] = left_list[i++];
    else
      list[k] = right_list[j++];
  }
}

void sort(int left, int right, int(*compar)(const void *, const void *))
{
  if (left < right)
  {
    // find the pivot point
    int mid = (left + right) / 2;

    // recursive step
    sort(left, mid, compar);
    sort(mid + 1, right, compar);

    // merge resulting sublists
    merge(left, mid, right, compar);
  }
}

然后,我几次使用不同的比较功能,在同一个“<><>>list/strong>阵列上打电话。我发现,这种说法在第一次呼吁中是稳定的,但此后,我看到一些要素被放弃,即使它们平等。

谁能提出这种行为的理由?

Answer 1

我不敢肯定这样做,而是试图改变这一思路:

compar(&left_list[i], &right_list[j]) < 0

为此:

compar(&left_list[i], &right_list[j]) <= 0

这将使它能够做到,如果它们已经平等,它就会采取首批行动,(全心全意)维护稳定,而不是把事情环绕。

这只是一种猜测。

Answer 2

我认为你的规模是错误的。

int left_size = mid - left;

And, as pointed by arasmussen, you need to give preference to the left list in order to mantain stability

compar(&left_list[i], &right_list[j]) <= 0

在接受所有这些要求时,你在填写求助人名单后,没有打电话。这不会使算法回归不正确的结果,而是将造成你的方案记忆被用于每当你称之为某种功能时都不可逆地增长。

友情链接