3

我正在尝试重新编写递归合并排序，例如

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功能）。

提前致谢。

4

1 回答 1

3

由于 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 时，商将被截断。

在 yourMergeSort_NonRecursive中，您将ints 划分为多个位置，例如i=i/2, j*size/i, size/i。注意你会得到的值。

于 2013-03-31T20:58:54.980 回答