c++ - 如何在冒泡排序中添加一个计数器来统计数字比较？

Question

考虑以下代码:

int CountBubbleSort=0;
template <typename Comparable>
void bubbleSort(vector<Comparable*> &v)
{
    bool sorted = false;
    for(int pass = 1; pass < v.size() && !sorted; pass++)
    {
        sorted = true;
        for(int i = 0; i < v.size() - pass; i++)
        {
            if(*v[i + 1] < *v[i])
            {
                swap(v, i, i + 1);
                CountBubbleSort++;
                sorted = false;

            }
        }
    }
    cout<<"bubbleSort comparison is "<<CountBubbleSort<<endl;
}

当我调用该函数时，为什么 CountBubbleSort 的输出是“0”，这是什么问题？

Answer 1

void bubbleSort(vector<Comparable*> &v)
{
    bool sorted = false;
    for(int pass = 1; pass < v.size() && !sorted; pass++)
    {
        sorted = true;
        int i;
        for(i = 0; i < v.size() - pass; i++)
        {
            if(*v[i + 1] < *v[i])
            {
                swap(v, i, i + 1);
                sorted = false;

            }
        }
        CountBubbleSort += i;
    }
    cout<<"bubbleSort comparison is "<<CountBubbleSort<<endl;
}

要计算比较的次数，您只需在第一个循环的每一轮将内部 i(在每个第二个循环中进行比较)添加到您的 countBubble 中。