大家好,对于一项作业,我们必须计算许多算法的比较次数。我正在使用 Sedgewick & Wayne 的“算法”一书中的代码。我实际上看不出我的代码哪里错了...只要我们要比较一些东西,我就会计算我的比较...
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;
}
有人对此有想法吗?帮助将不胜感激!
最佳答案
比较次数应该正好是 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
}
关于java - 插入排序,比较次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29188078/