计算 C++ 插入排序中的比较次数

Question

我正在使用交换辅助函数对数组进行简单的插入排序；我正在尝试对比较和交换进行计数，并且我能够计算出交换计数，但我无法计算出比较。

在函数中，我写道，对于每次交换，本质上都有一个比较（我认为），这是在 while 循环中，但我试图弄清楚如何表明即使在交换尚未发生。

int swaps = 0;
int comparisons = 0;

void InsertionSort(int numbers[], int size) {
   int i;
   int j;
   for (i = 1; i < size; ++i) {
      j = i;
      while (j > 0 && numbers[j] < numbers[j - 1]) {
            comparisons++;
            Swap(numbers, j, j  - 1);
            swaps += 1;
            j--; 
      }
      PrintNums(numbers, size); 
      }   
   }

Answer 1

传递比较参数：

template <typename Less = std::less<int>>
void InsertSort(int* const numbers, std::size_t const size, Less const less = Less{}) {
  for (std::size_t i = 1; i < size; ++i) {
    for (std::size_t j = i; j > 0 && less(numbers[j], numbers[j - 1])) {
      std::swap(numbers[j], numbers[j-1]);
      j--; 
    }
  }   
}

int main() {
  int numbers[] = {3,45,1,5,2,0};
  std::size_t comparisons = 0;
  InsertSort(numbers, std::size(numbers), [&comparisons](int a, int b) {
    ++comparisons;
    return a < b;
  });
  PrintNums(numbers, std::size(numbers));
}

请注意，交换不被计算在内，但您可以轻松地调整此习惯用法来计算交换。