c++ - shell 排序中的交换和比较

Question

我试图弄清楚如何找到 shell 排序函数中使用的交换和比较的总量，但我不太确定在哪里放置交换和比较的添加。

我在下面的这个 insertionSort 函数中添加了一些内容。

void insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = startIndex + gap; i < numbersSize; i += gap) {
        j = i;
        while (j - gap >= startIndex && numbers[j] < numbers[j - 1]) {
            temp = numbers[j];
            numbers[j] = numbers[j - gap];
            numbers[j - gap] = temp;
            j = j - gap;
            totalComps++; //declared globally
            totalSwaps++; //declared globally
        }

    }
}

我知道 totalSwaps 就在它所在的位置很好，但我不太确定将 totalComps 放在哪里，因为我们也在 while 循环中进行比较。

Answer 1

您可以使用一对 function objects ，一个进行比较，另一个进行交换。

struct counted_less
{
    int count = 0;
    bool operator()(int lhs, int rhs)
    {
        ++count;
        return lhs < rhs;
    }
}

struct counted_swap
{
    int count = 0;
    void operator()(int & lhs, int & rhs)
    {
        ++count;
        using std::swap;
        swap(lhs, rhs);
    }
}


std::pair<int, int> insertionSortInterleaved(int numbers[], int numbersSize, int startIndex, int gap) {
    counted_less less;
    counted_swap swap;

    for (int i = startIndex + gap; i < numbersSize; i += gap) {
        for (int j = i; j - gap >= startIndex && less(numbers[j], numbers[j - 1]); j -= gap) {
            swap(numbers[j], numbers[j - gap]);
        }
    }

    return { less.count, swap.count };
}