插入比較＃似乎太大

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，因此比你預期的要低，低於。