Mergesort交换和比较

Question

我正在研究一个分析项目,我正在观察在Java中实现时不同算法的行为方式.我得到了一些从在线实现Mergesort算法的代码,现在我需要在10,000个随机生成的整数(1到100,000之间)的数组上运行此代码,并记录进行了多少次交换和比较.

我不确定代码中的哪一点增加了计算Swaps和Comparisons的变量.期望值是多少？因为Mergesort的最佳,最差和平均情况都是nlog(n)这是否意味着我应该期望10,000*(10,000的基数2)约为138,000,交换和比较的总和？

这是代码,我猜测交换仅在原始数组被更改时发生,比较我不太确定:

void MergeSort(int low, int high)
   // a[low : high] is a global array to be sorted.
// Small(P) is true if there is only one element to
// sort. In this case the list is already sorted.
{
   if (low < high) { // If there are more than one element
          // Divide P into subproblems.
          // Find where to split the set.
          int mid = (low + high)/2;
          // Solve the subproblems.
          MergeSort(low, mid);
          MergeSort(mid + 1, high);
          // Combine the solutions.
          Merge(low, mid, high);
   }
}

   void Merge(int low, int mid, int high)
 // a[low:high] is a global array containing two sorted
 // subsets in a[low:mid] and in a[mid+1:high]. The goal
 // is to merge these two sets into a single set residing
 // in a[low:high]. b[] is an auxiliary global array.
 {
     int h = low, i = low, j = mid+1, k;
   while ((h <= mid) && (j <= high)) {
      if (a[h] <= a[j]) { b[i] = a[h]; h++; }
      else { b[i] = a[j]; j++; } i++;
   }
   if (h > mid) for (k=j; k<=high; k++) {
                   b[i] = a[k]; i++;
                }
   else for (k=h; k<=mid; k++) {
           b[i] = a[k]; i++;
        }
   for (k=low; k<=high; k++) a[k] = b[k];

}

Answer 1

我不确定代码中的哪一点增加了计算Swaps和Comparisons的变量.

我建议你为交换和比较操作创建帮助方法.这将为您提供增量计数器代码的好地方.

因为Mergesort的最佳,最差和平均情况都是nlog(n)这是否意味着我应该期望10,000(10,000的基数为2)约为138,000的掉期和比较总和？*

你可以期待的是,比较的数量与n log(n)成比例,其中输入的大小是n.