Java 归并排序 : Compare and Swap Counters

Question

我有以下 MergeSort 类，我必须实现比较和交换计数器。有人可以确认我的比较和交换计数器是否位于正确的位置吗？

正如您将看到的，我有两个用于交换和比较计数器的类属性。我不太肯定的地方是A)我初始化swapCount和compareCount(在runSort方法或mergeSort方法中？)和B)merge方法中的swapCount++应该放置在哪里。我很确定compareCount++ 是在正确的地方。

这是代码。预先感谢所有回复的人!

public class MyMergeSort {

    private int swapCount;
    private int compareCount;

    public void runSort() {
        //this.compareCount = 0;
        //this.swapCount = 0;

        mergeSort(this.sortItems,0,sortItems.length);
    }

    public void mergeSort(String[] data, int first, int n) {

        int n1; // Size of the first half of the array
        int n2; // Size of the second half of the array
        this.compareCount = 0;
        this.swapCount = 0;

        if (n > 1) {
            // Compute sizes of the two halves
            n1 = n / 2;
            n2 = n - n1;

            mergeSort(data, first, n1);      // Sort data[first] through data[first+n1-1]
            mergeSort(data, first + n1, n2); // Sort data[first+n1] to the end

            // Merge the two sorted halves.
            merge(data, first, n1, n2);
        }

    }

    private void merge(String[] data, int first, int n1, int n2) {

        String[] temp = new String[n1+n2]; // Allocate the temporary array
        int copied  = 0; // Number of elements copied from data to temp
        int copied1 = 0; // Number copied from the first half of data
        int copied2 = 0; // Number copied from the second half of data
        int i;           // Array index to copy from temp back into data

        // Merge elements, copying from two halves of data to the temporary array.
        while ((copied1 < n1) && (copied2 < n2)) {

            compareCount++;

            if (data[first + copied1].compareTo(data[first + n1 + copied2]) < 0) {
                temp[copied++] = data[first + (copied1++)];

                //swapCount++;

            }
            else {
                temp[copied++] = data[first + n1 + (copied2++)];

                swapCount++;
            }
        }

        // Copy any remaining entries in the left and right subarrays.
        while (copied1 < n1)
            temp[copied++] = data[first + (copied1++)];
        while (copied2 < n2)
            temp[copied++] = data[first + n1 + (copied2++)];

        // Copy from temp back to the data array.
        for (i = 0; i < n1+n2; i++)
            data[first + i] = temp[i];
    }

}

** 更新 11/28/2017 ** 好消息。我想我终于找到了我正在寻找的东西:

http://www.cs.carleton.edu/faculty/adalal/teaching/f04/117/notes/nov08/Sort.java

非常感谢该代码的作者!

Answer 1

为了实现正确的计数，您需要在每次发生计数的事情时增加计数值。例如:

if (n > 2) {
   a = b;
   swapCount++;
}
compareCount++; // because the condition of the if statement

这意味着您可能需要构建您的方法，以便可以访问 swapCount 和 compareCount，并重新设计您的逻辑，以便短路不会偏离实际计数。例如，你不能写

if ((a > 5) && (b > 5)) {
  ...
}

并获得一种更新compareCount的简单方法，因为您需要添加逻辑来查看是否完成了一次比较或两次比较。为此，您至少需要添加一个额外的比较

if (a > 5) {
   compareCount++;
} else {
   compareCount += 2;
}

相反，用不同的方式简单地编写复合比较会更好

if (a > 5) {
   if (b > 5) {
   }
   compareCount++;
}
compareCount++;

在“if 语句”中读起来更差，但在确定递增 compareCount 的条件时更清晰。