插入比较＃似乎太大

Question

我很困惑，如果这些比较数字应该是100个随机两位数字的向量值这么大。完整程序 - >安全链接：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个元素的向量，因此预期的比较次数为O(10000)。以2656出场，或者在你的第二轮比赛中，4995，因此比你预期的要低，低于。