java无法获得正确的插入排序键比较数
我正在努力解决插入排序键比较和交换计数的数量问题
我有一种方法,可以在最后计算并打印出关键的比较结果
public static void insertionSort(int[] array) {
int n = array.length;
int cm = 0;
int sw = 0;
for (int pass = 0; pass < array.length; pass++) {
// figure out what should go into a[pass]
int min = pass;
for (int j = pass + 1; j < array.length; j++) {
if (smaller(array, j, min)) {
cm++;
min = j;
}
}
swap(array, pass, min);
sw++;
}
System.out.print("Insertion sort: ");
for (int c = 0; c < n; c++) {
System.out.print(array[c] + " ");
}
System.out.println("- " + cm + " comparisons, " + sw + " swaps");
}
private static void swap(int[] a, int i, int j) {
if (i != j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
private static boolean smaller(int[] a, int i, int j) {
//another suggestion came up to call a count variable here because a false comparison could still count as a comparison
count++;
if (a[i] < a[j]) {
return true;
}
return false;
}
用这个测试阵列
int[] test = {13, 12, 5, 6, 11};
我应该得到7比较和4交换,但我得到了5比较和5交换。 使用另一个从0到31的数组(测试最佳情况), 我得到0比较和32交换
# 1 楼答案
更新以获取答案。 这适用于比较计数,但仍适用于交换计数