插入排序，比较次数

Question

大家好，对于一项作业，我们必须计算多种算法的比较次数。我使用的是 Sedgewick & Wayne 所著 "Algorithms" 一书中的代码。我实际上没有看到我的代码哪里错了......一旦我们要比较一些东西我就会计算我的比较......

public long sort(Comparable[] a) {
        if (a == null) {
            throw new IllegalArgumentException("argument 'array' must not be null.");
        }
        int N = a.length;
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0; j--) {
                this.comparisons++;
                if(less(a[j], a[j-1]))
                    exch(a, j, j-1);      
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
        return this.comparisons;
    }

我用的less方法：

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

必须通过这个测试

Integer[] array = {4, 2, 1, 3, -1};
        Comparable[] arrayClone1 = array.clone();
        Comparable[] arrayClone2 = array.clone();
        long nbCompares1 = i.sort(arrayClone1);
        long nbCompares2 = i.sort(arrayClone2);
        System.out.println("1" + nbCompares1);
        System.out.println("2" + nbCompares2);

这两个应该相等....

isSorted 方法：

 private boolean isSorted(Comparable[] a) {
        System.out.println("here");
        return isSorted(a, 0, a.length - 1);
    }

    // is the array sorted from a[lo] to a[hi]
    private boolean isSorted(Comparable[] a, int lo, int hi) {
        System.out.println("here1");
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }

有人对此有想法吗？帮助将不胜感激！

Answer 1

比较次数应该正好是N*(N-1)/2。也许你在其他地方弄乱了 comparisons 字段，所以我建议改用局部变量：

public long sort(Comparable[] a) {
        if (a == null) {
            throw new IllegalArgumentException("argument 'array' must not be null.");
        }
        int N = a.length;
        int comparisonsCount = 0; // use this instead
        for (int i = 0; i < N; i++) {
            for (int j = i; j > 0; j--) {
                comparisonsCount++; // edit here
                if(less(a[j], a[j-1]))
                    exch(a, j, j-1);      
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
        return comparisonsCount; // and here
    }

插入排序，比较次数

Insertion sort, number of comparisons

java

algorithm

sorting

insertion-sort