计算合并排序 (Java) 中的交换次数

Question

我试图查找数组中元素交换以对数组进行排序的次数。该程序使用递归和合并排序。在尝试多次将计数器放入我相信排序发生的位置后，我得到了看起来像随机生成的数字作为交换次数。

这是代码。我只想要一个显示正确掉期金额的数字，而不是随机数。

/**
* 
* @author Frank Stalteri
*
*/
public class mergeExample {
/**
* 
* @param args
*/
public static void main(String[] args) {
int [] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
/**
* performs merge sort
*/
mergeSort(list);
/**
* prints array to screen
*/
printArray(list);
}
/**
* 
* @param list
*/
public static void mergeSort(int [] list) {
if (list.length > 1) {
/**
* merge first half of array
*/
int [] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
/**
* merge second part of array
*/
int secondHalfLength = list.length - list.length / 2;
int [] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
/**
* put the sorted parts together
*/
merge(firstHalf, secondHalf, list);
}
}
/**
* 
* @param list1
* @param list2
* @param temp
* @return 
*/
public static void merge(int [] list1, int [] list2, int [] temp) {
int current1 = 0;   //current index in list1
int current2 = 0;   //current index in list2
int current3 = 0;   //current index in temp
while (current1 < list1.length && current2 < list2.length) {
if (list1[current1] < list2[current2]) {
temp[current3++] = list1[current1++];
}
else {
temp[current3++] = list2[current2++];
}
}
while (current1 < list1.length) {           
temp[current3++] = list1[current1++];
}
while (current2 < list2.length) {
temp[current3++] = list2[current2++];
}
}
/**
* 
* @param list
*/
public static void printArray(int [] list) {
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}

这是输出

1
1
1
2
0
0
1
2
5
-2 1 2 2 3 3 5 6 12 14 

Answer 1

您必须在合并函数之外添加类似计数变量的内容，例如作为类中的static int：

public class MergeExample {
static int mergeCount = 0;
// ...
}

每当您在mergeSort函数中对代码进行交换时，都必须将MergeExample.mergeCount递增 1。最后，您将在该变量中执行交换次数。