c++ - 归并排序中选择中间元素

Question

对于下面给定的合并排序代码:

void merge(int a[], int bottom, int top, int mid){
    int i = bottom;
    int j = mid+1;
    int k = bottom;
    int c[50];

    while (i <= mid&&j <= top){
         if(a[i]<=a[j]){
         c[k] = a[i];
         i++;
         k++;
         }
     else{
         c[k] = a[j];
         j++;
         k++;
         }
    }

    while (i <= mid){
     c[k] = a[i];
     k++;
     i++;
    }

    while (j <= top){
     c[k] = a[j];
     k++;
     j++;
    }

    for (int i = bottom; i < k; i++){
     a[i] = c[i];   
    }
}

void mergesort(int a[], int bottom, int top){
    if(bottom < top){
     int mid = (bottom+top)/2;
     mergesort(a, bottom, mid);
     mergesort(a, mid+1, top);
     merge(a, bottom, top, mid);
    }
}

如果将合并排序调用更改为

mergesort(a, bottom, mid-1);
mergesort(a, mid, top);

这会导致运行时错误。

从算法方面来看，我没有看到任何差异。有人可以指出这一更改有什么问题吗？

Answer 1

假设底部为 0，顶部为 1，因为您调用了 mergesort(a, 0, 1) 。那么 mid = (0+1)/2 = 0。然后 mid-1 = -1。那么您调用mergesort(a, 0, -1)和mergesort(a, 0, 1) (注意...这是我们开始的调用)。第一个调用将返回，因为它与 bottom < top 不匹配条件，但第二个是无限递归。

如果您注意到，此问题适用于 mergesort(a, n, n + 1) 形式的所有调用，并且由于合并排序是一种分而治之类型的算法，因此您将非常频繁地进行此类调用。