java - 了解 Java 中合并排序算法的关键操作计数

Question

我正在评估合并排序算法并对关键操作进行计数。虽然从技术上讲这是家庭作业，但它来自之前的作业，代码是缩小版本，仅显示有问题的区域。我试图更好地理解我的问题并调试我的关键操作计数以准确描述。

该项目是实现合并排序并对其进行评估。关注的领域是计算关键操作并通过随机填充具有 10 个不同大小的数组来确定计数的偏差，每个大小运行 50 次不同的时间(使用不同的随机数据)。我的发现是，对于每个大小，关键操作的数量总是以相同的方式结束(例如，大小为 10 的数组达到 68 个关键操作，而不管数据如何)，关键操作偏差为 0。

教授说这是不准确的，我的程序有问题，因为它应该为每个数组长度的不同数据产生不同的计数。我试图弄清楚我的程序中有什么不准确的地方导致了这个问题。我已经检查过每次传递是否产生不同的数组数据，并且这些数据是否被传递给排序算法并正确排序。

下面是我编写的代码，同样，无论数据如何，它仍然会产生相同的关键操作数。谁能指出我的问题？无论我对计数做什么，它总是产生相同的值。

public class MergeSortSingle {
public static int count = 0;

private MergeSortSingle() { }

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        count++;
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid) {
            count++;
            a[k] = aux[j++];
        }
        else if (j > hi) {
            count++;
            a[k] = aux[i++];
        }
        else if (less(aux[j], aux[i])) {
            count++;
            a[k] = aux[j++];
        }
        else      {
            count++;
            a[k] = aux[i++];
        }
    }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length-1);
}

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

private static void show(Comparable[] a) {
    System.out.println("\nAfter Sorting completed:");
   System.out.print(Arrays.toString(a));
   System.out.println();
}

public static void main(String[] args) {
    int length = 10;
    Comparable[] a = new Comparable[length];
    for (int w = 0; w < length; w++) {
            a[w] = (int) (Math.random() * 10000 + 1);
        }
    System.out.println("Before Sorting:");
    System.out.print(Arrays.toString(a));
    System.out.println();
    MergeSortSingle.sort(a);
    show(a);
    System.out.println("\nCounter = " + count);
}
}

示例输出 1:

排序前: [9661, 4831, 4865, 3383, 1451, 3029, 5258, 4788, 9463, 8971]

排序完成后: [1451, 3029, 3383, 4788, 4831, 4865, 5258, 8971, 9463, 9661]

计数器 = 68

示例输出 2:

排序前: [9446, 230, 9089, 7865, 5829, 2589, 4068, 5608, 6138, 372]

排序完成后: [230, 372, 2589, 4068, 5608, 5829, 6138, 7865, 9089, 9446]

计数器 = 68

合并排序代码来自: http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

Answer 1

您只在合并子数组时计数 - 您使用计数器复制数组 tro aux - 这将始终是相同数量的操作，然后您在 for 处再次使用它循环 - 那里有 4 条路径，每条路径都会递增计数器 - 同样，固定次数。
你还必须在 sort 计算比较- if (hi <= lo) - 这是一个操作。如果失败 - 这是另一个操作。