Mergesort交换和比较

我正在研究一个分析项目，我正在观察在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]  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 。

Answer 2

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

  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++; } 

Answer 3

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

在您的合并方法中

 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语句中放置一个计数器，它将计算所有交换。 我通过检查数组两次确认了这个，一次是未排序的，另一次是排序的。 我不是百分之百，所以任何反馈都表示赞赏。 在我的作业中看起来有点容易，因为我正在排序字符串，这些是上面发布的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是在构造函数中设置的类变量。 如果我记得这个方法，我可以重置它们。