合并排序和选择排序的计数操作

Question

我想要比较排序算法合并排序和选择排序的操作计数，但我在计算哪些操作和不计算哪些操作时遇到了一些问题。

下面是我的实现。我想我正在以正确的方式计算选择排序的操作，但我不知道合并排序：

选择排序：

public class SelectionSort {
private int exchanges, comparisons;

public void selectionSort(int[] x) {    
    for (int i=0; i<x.length-1; i++) {
        for (int j=i+1; j<x.length; j++) {
            if (x[i] > x[j]) 
            {
                //... Exchange elements
                int temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                exchanges++;
            }
            comparisons++;
        }
    }
    System.out.println("SelSort_Exchanges: "+exchanges);
    System.out.println("SelSort_Comparisons: "+comparisons);
    System.out.println("SelSort_Operations: "+(exchanges+comparisons));
}
}

如果我放入一个包含10个int的数组，我会得到：

SelSort_Comparisons: 45
SelSort_Exchanges: 27
SelSort_Operations: 72

在我看来似乎是对的，但现在是合并排序：

public class Mergesort {
private int[] numbers;
private int[] helper;

private int number;
private int comparisons, exchanges;

public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
    System.out.println("MerSort_Comparisons "+comparisons);
    System.out.println("MerSort_Exchanges "+exchanges);
    System.out.println("MerSort_Operations "+(comparisons+exchanges));
    System.out.println();
}

private void mergesort(int low, int high) {
    // Check if low is smaller then high, if not then the array is sorted
    if (low < high) 
    {
        // Get the index of the element which is in the middle
        int middle = (low + high) / 2;
        // Sort the left side of the array
        mergesort(low, middle);
        // Sort the right side of the array
        mergesort(middle + 1, high);
        // Combine them both
        merge(low, middle, high);
    }
}

private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
        helper[i] = numbers[i];
        exchanges++;
    }
    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
        if (helper[i] <= helper[j]) {
            numbers[k] = helper[i];
            i++;
            exchanges++;
        } else {
            numbers[k] = helper[j];
            j++;
            exchanges++;
        }
        k++;
        comparisons++;

    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
        numbers[k] = helper[i];
        exchanges++;
        k++;
        i++;
    }
}   
}

现在我得到了

MerSort_Comparisons 22
MerSort_Exchanges 61
MerSort_Operations 83

但我不知道这是否正确。比较的结果对我来说似乎是正确的，但如果我以20个数组为例，它似乎不再正确。

有没有人能帮我解决这个问题，告诉我我应该把比较和交换增量放在哪里？

提前感谢！:)

Answer 1

最简单的方法是创建两个方法，Compare和Swap，并在其中增加计数器。无论您实现什么sorting algorithm，它都应该只使用这些方法与数组交互。

此外，this page还可以帮助您直观地分析不同的排序算法。