合并排序中的交换次数计数(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

你必须在你的合并函数之外添加一些类似于counter变量的东西，比如说作为一个 static int 在你的类中。

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

每当你在你的代码中做一个交换的时候 mergeSort 函数，你必须增加 MergeExample.mergeCount 最后，您将在该变量中得到执行的交换次数。