中的std ::排序（）

Question

我怎麼能算排序與正整數的向量時發生在標準C++ STL排序函數比較的數量做比較的次數？

Answer 1

一種快速，非侵入性的方法是使用lambda函數。你可以，如果你使用的是C++ 11或以上，所以像下面使用lambda：

unsigned int numComparisons = 0U; 
std::vector<unsigned int> someContainer; 
// Fill container, etc. 
std::sort( 
    std::begin(someContainer), 
    std::end(someContainer), 
    [&numComparisons](unsigned int lhs, unsigned int rhs) 
    { 
     ++numComparisons; 
     return lhs < rhs; 
    } 
); 

std::cout << numComparisons << " comparisons were performed in std::sort" << std::endl; 

Answer 2

爲了補充觀測的方法，你可以閱讀the documentation。在複雜度上，std::sort必須是：

O（N·log（N）），其中N = std ::距離（第一次，最後一次）平均比較。 （直到C++ 11）

O（N·log（N）），其中N = std :: distance（first，last）比較。 （因爲C++ 11）

顯然，大O符號可以掩蓋某些恆定的因素，但一般地，希望它是相稱N·日誌（N）（其中對數是基體2，像所有優秀的CS日誌）。