java - 计算排序过程中进行比较和移动的次数

Question

我正在做插入排序，想知道比较次数和移动次数是否计算正确。比较是比较两个值的次数，移动是移动元素的数量，因此数字之间的交换将是 2 次移动。

public static int[] InsertionSort(int[] a) {
    int j;
    for(int i = 1; i < a.length; i++) {
        int tmp = a[i];
        for(j = i; j > 0 && (tmp < a[j-1]); j--) {
            numCompares++;
            a[j] = a[j-1];
            numMoves++;
        }
        a[j] = tmp; 
        numMoves++;
    }
    return a;
}

Answer 1

这里唯一的问题是在内循环条件下j > 0 && (tmp < a[j-1]) ，实际对比tmp < a[j-1]可能结果为 false，导致 for 中断循环，所以numCompares++位于循环内部的内容将被跳过。为了精确地计算比较，需要进行小的重新格式化:

for(j = i; j > 0; j--) {
    numCompares++; 
    if (tmp >= a[j - 1])
        break; 
    a[j] = a[j - 1];
    numMoves++;
}