c - C中的顺序归并排序

Question

我正在尝试重写一个递归合并排序

void MergeSort(int* data, int size){
  int half=size/2;
  if (size > 1) {
    MergeSort(data, half);
    MergeSort(data+half, half);
    Merge(data, size);
  }
}

其中

void Merge(int* data, int size){
  int cnt;
  int cntLow=0;
  int half=size/2;
  int cntHigh=half;
  int* sorted;

  sorted = (int*) malloc(size*sizeof(int));

  for (cnt=0; cnt<size; cnt++){
    if (cntLow == half) 
      sorted[cnt] = data[cntHigh++];
    else if (cntHigh == size)
      sorted[cnt] = data[cntLow++];
    else if (data[cntLow] <= data[cntHigh])
      sorted[cnt] = data[cntLow++];
    else
      sorted[cnt] = data[cntHigh++];
  }

  for (cnt=0; cnt<size; cnt++)
    data[cnt] = sorted[cnt];

  free(sorted);
}

非递归调用。所以我写了函数

void MergeSort_NonRecursive(int* data, int size){
    int i;
    int j;

    for (i=size; i>0; i=i/2){
        for (j=0; j<i; j++){
            Merge(data + j*size/i, size/i);
        }
    }
}

这显然适用于大小为 $2^n$ 的序列。然而，当我在大小不同于 $2^n$ 的序列中运行它时，它没有正确排序，所以在 MergeSort_NonRecursive 的某些地方，我的代码一定是错误的。

那么我哪里做错了(在 MergeSort_NonRecursive 中)？ (另外，我需要使用 Merge 函数)。

提前致谢。

Answer 1

因为 size 是一个 int，size/2 会截断你的商。

例如如果 size=4，size/2 = 2。如果 size=5，size/2 = 2。如果 size=6，size/2 = 3。

因此对于 5 的大小，您希望第一次 MergeSort 递归调用 size/2 元素(即前 3 个)上的运算符，第二次调用对剩余的 2 个元素进行操作。

你可以说例如

int half = size/2; //size = 5: half = 2
int rest = size - half; //rest = 3

所以:

void MergeSort(int* data, int size){
  int half=size/2;
  int rest = size-half;
  if (size > 1) {
    MergeSort(data, half);
    MergeSort(data+half, rest); //changed this line
    Merge(data, size);
  }
}

编辑:

在我发布后，您似乎稍微更改了问题。总体思路仍然成立:当您将一个 int 除以另一个 int 时，商会被截断。

在您的 MergeSort_NonRecursive 中，您在多个地方划分 int，例如i=i/2，j*size/i，size/i。注意您将获得的值。