java - 合并排序比较？

Question

我认为在返回比较次数的合并排序 2 类/方法中使用合并排序的比较次数不正确。归并排序 2 类似于归并排序，但仅返回比较的数量。下面是我的演示，我有一个由 4 个整数组成的数组 {2,55,1,45}，当我运行该程序时，它返回 8 个比较。谁能验证这是否正确或我做错了什么？

我的演示:

    ArrayInts[] myInts2 = new ArrayInts[4];

    myInts2[0] = new ArrayInts(2);
    myInts2[1] = new ArrayInts(55);
    myInts2[2] = new ArrayInts(1);
    myInts2[3] = new ArrayInts(45);

    MergeSort.mergeSort(myInts2, 0, 3);

    System.out.println("Sorted using Merge Sort: ");


    for (int index = 0; index < myInts2.length; index++) {
        System.out.println(myInts2[index]);
    }

    System.out.println("Number of comps using Merge Sort: " + MergeSort2.mergeSort2(myInts2, 0, 3));
    System.out.println(" ");

我的合并排序2类/方法:

 public class MergeSort2 {
 private static long comp=0;

public static <T extends Comparable<? super T>> long mergeSort2(T[] data, int min, int max) {
    T[] temp;
    int index1, left, right;


    //return on list of length one

    if (min == max) {
        return comp;
    }

    //find the length and the midpoint of the list

    int size = max - min + 1;
    int pivot = (min + max) / 2;
    temp = (T[]) (new Comparable[size]);

    mergeSort2(data, min, pivot); //sort left half of list
    mergeSort2(data, pivot + 1, max); //sort right half of list

    //copy sorted data into workspace

    for (index1 = 0; index1 < size; index1++) {
        temp[index1] = data[min + index1];
    }

    //merge the two sorted lists

    left = 0;
    right = pivot - min + 1;
    for (index1 = 0; index1 < size; index1++) {
        comp++;
        if (right <= max - min) {

            if (left <= pivot - min) {

                if (temp[left].compareTo(temp[right]) > 0) {

                    data[index1 + min] = temp[right++];
                } else {
                    data[index1 + min] = temp[left++];
                }
            } else {
                data[index1 + min] = temp[right++];
            }
        } else {
            data[index1 + min] = temp[left++];
        }
    }


    return comp;

    }

    }

Answer 1

您得到的是 8，因为无论是否进行比较，每次执行合并循环时您都会递增。

如果你改变

for (index1 = 0; index1 < size; index1++) {
    comp++;
    if (right <= max - min) {

        if (left <= pivot - min) {

至

for (index1 = 0; index1 < size; index1++) {
    if (right <= max - min) {

        if (left <= pivot - min) {
            comp++;

您将获得进行比较的次数，而不是循环迭代的次数。

[0,1,2,3] 应该产生 4 个比较
[3,2,1,0] 应该产生 4 个比较
[0,2,1,3] 应该产生 5 个比较
[0,4,1,5,2,6,3,7] 应产生 16 个比较

归并排序是一种 O(nlog2n) 最坏情况算法。

你还需要改变这一点

MergeSort.mergeSort(myInts2, 0, 3);

System.out.println("Sorted using Merge Sort: ");


for (int index = 0; index < myInts2.length; index++) {
    System.out.println(myInts2[index]);
}

System.out.println("Number of comps using Merge Sort: " + MergeSort2.mergeSort2(myInts2, 0, 3));
System.out.println(" ");

至

int result = MergeSort.mergeSort(myInts2, 0, 3);

System.out.println("Sorted using Merge Sort: ");


for (int index = 0; index < myInts2.length; index++) {
    System.out.println(myInts2[index]);
}

System.out.println("Number of comps using Merge Sort: " + result);
System.out.println(" ");

因为当你输出计数时 myInts 将会被排序，这样你就可以得到排序后的复杂度。

演示多次调用排序的效果。

public static void main(String[] args) {
    Integer[] myInts2 = new Integer[4];

    myInts2[0] = new Integer(0);
    myInts2[1] = new Integer(2);
    myInts2[2] = new Integer(1);
    myInts2[3] = new Integer(3);

    System.out.println(new MergeSort2().mergeSort2(myInts2, 0, 3)); // will output 5
    System.out.println(new MergeSort2().mergeSort2(myInts2, 0, 3)); // will output 4
}

第二次调用排序将使用排序数据而不是未排序数据，因此您将得到不同的结果。对数组进行排序可以修改数组，因此调用排序倍数不同的时间会有不同的行为。