c++ - 插入比较 #'s 似乎太大了

Question

对于具有 100 个随机两位数的 vector ，如果这些比较数字的值应该这么大，我感到很困惑。完整程序 --> 安全链接:https://ideone.com/oybDbD程序输出位于链接的底部。感谢输入。

int insertionSort (vector<int> &v) {
    int j, temp, counter = 0;

    for (int i = 1; i < v.size(); i++) {
        j = i;

        while (++counter && j > 0 && v[j] < v[j-1]){
            temp = v[j];
            v[j] = v[j-1];
            v[j-1] = temp;
            j--;
        }
    }
    return counter;
}

Answer 1

插入排序的平均情况下性能是 O(N^2)(参见 wiki entry)。因此，对于包含 100 个元素的 vector ，预期的比较次数为 O(10000)。结果是 2656，或者在你的第二次运行中，结果是 4995，因此，比较值低于你可能预期的值。