C语言 计算合并排序的比较次数

Question

所以这是我的合并排序代码。但是我需要找出在合并函数期间进行了多少次比较。对于我的代码，计数输出将为 0。我应该如何更改代码以使计数器工作？

#include<stdio.h>
#include<stdlib.h>
void merge(int *array,int low, int mid, int high,int count)
{
  int i=low, j=mid+1, n=low, f[high+1];
  while((i<=mid)&&(j<=high)) {
    if(array[i]>array[j]){
          f[n]=array[j];
          j++;
      }else{
          f[n]=array[i];
          i++;
      }
    n++;
    count++;
  }
  if(i>mid)
  while(n<=high) {
    f[n]=array[j];
    n++;
    j++;
    }
  if(j>mid)
  while(n<=high) {
    f[n]=array[i];
    n++;
    i++;
    }
  for(n=low;n<=high;n++)
      array[n]=f[n];
}

void mergesort(int *array, int low, int high,int count)
{
  int mid;
  if(low<high){
      mid=(high+low)/2;
      mergesort(array,low,mid,count);
      mergesort(array,mid+1,high,count);
      merge(array, low, mid, high,count);
     }
} 
int main()
{
  int size,i, count=0, *f;
  scanf("%d", &size);
  f=(int *)malloc(sizeof(int)*size);
  for(i=0;i<size;i++)
    scanf("%d", &f[i]);
  mergesort(f, 0, size-1,count);
  for(i=0;i<size;i++) {
      printf("%d",f[i]);
      if(i==size-1)
        printf("n");
      else
        printf(" ");
    }
  printf("%dn", count);
  return 0;
}

Answer 1

实现

此目的的最简单方法是count有一个全局变量，并且每次在 Mergesort 代码中进行比较时都会递增该变量。要么那个，要么使用指针。

在 C 中，当您将参数传递给函数时，该参数将被复制，因此原始参数将保持不变。这就是你的代码的问题。

请在此处阅读更多内容：为什么要在 C 中按值传递函数参数？