2

我目前正在从事一个分析项目，我正在观察在 Java 中实现不同算法时的行为方式。我从网上得到了一些实现 Mergesort 算法的代码，现在我需要在一个由 10,000 个随机生成的整数（介于 1 到 100,000 之间）组成的数组上运行此代码，并记录进行了多少交换和比较。

我不确定在代码中的哪一点增加计算交换和比较的变量。期望值是多少？由于 Mergesort 的最佳、最差和平均情况都是 nlog(n)，这是否意味着我应该期望 10,000*(log base 2 of 10,000) 大约 = 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];

}

4

3 回答 3

6

我不确定在代码中的哪一点增加计算交换和比较的变量。

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

由于 Mergesort 的最佳、最差和平均情况都是 nlog(n)，这是否意味着我应该期望交换和比较的总和为 10,000（10,000 的对数基数 2）约 = 138,000？*

您可以预期的是，比较次数与输入大小为 n 的n log(n)成正比。

于 2012-07-29T21:08:52.547 回答
1

在您的合并函数中，我添加了一个变量计数，它将完成总交换次数

  while ((h <= mid) && (j <= high)) {
      if (a[h] <= a[j]) { b[i] = a[h]; h++; }
      else { b[i] = a[j]; j++; count+=mid-h+1; } i++;
  }
于 2013-08-02T23:03:37.077 回答
0

我实际上是在为算法和数据结构中的作业做这个。线程有点尘土飞扬，但对于任何可以使用它的人来说，这就是我得到的：

在您的合并方法中

while ((h <= mid) && (j <= high)) {
  if (a[h] <= a[j]) { b[i] = a[h]; h++; }
  else { b[i] = a[j]; j++; } i++;
}

if 语句是进行比较的地方，我几乎想说，即使你对 else 语句进行比较，也会因为 if 语句失败而进行比较。

else 语句是开始进行交换的地方，如果您在 else 语句中放置一个计数器，它将计算所有交换。我通过两次检查数组来确认这一点，一次是未排序的，另一次是排序的。我对此不是 100%，所以任何反馈都表示赞赏。在我的作业中更容易看到，因为我正在对字符串进行排序，这些与上面发布的 Merge 函数中的行相同，来自我的作业：

while(leftPos<=leftEnd && rightPos<=rightEnd)
{
    mergeSortComparisons++;

    if (a[leftPos].compareTo(a[rightPos]) <= 0)     
        tmpArray[tmpPos++]=a[leftPos++];

    else 
    {
        tmpArray[tmpPos++]=a[rightPos++];
        mergeSortSwaps++;
    }
}

mergeSortSwaps 和 mergeSortComparisons 是在构造函数中设置的类变量。如果我记得方法，我可以重置它们。

于 2012-11-07T02:32:09.987 回答