c++ - 计算冒泡排序中交换和比较次数的问题

Question

我知道逆序列表应该产生 theta(n^2) 次比较和 theta(n^2) 次冒泡排序交换。在我的示例代码中，我使用了一个大小为 n = 10 的列表。我为 numComparisons 和 numExchanges 实现了计数器，虽然这看起来并不复杂，但我无法弄清楚为什么我的结果没有产生 100 次比较和100次交换。我真的离目标很远吗？

void testList::bubbleSort()
{

    int k = 10;
    bool flag = true;

    while(flag)
    {
        k = k - 1;
        flag = false;

        for(int j = 0; j < k; j++)
        {
            if( vecPtr[j] > vecPtr[j+1])
            {   


                int temp = vecPtr[j];
                vecPtr[j] = vecPtr[j+1];
                vecPtr[j+1] = temp;
                numExchanges += 1;
                flag = true;
            }
            numComparisons++;
        }
    }
}

结果输出:

原始列表:10 9 8 7 6 5 4 3 2 1

排序列表:1 2 3 4 5 6 7 8 9 10

比较:45

交易所:45

我也试过这个实现，但我的结果是一样的:

void testList::bubbleSort()
{

    int temp;
    for(long i = 0; i < 10; i++)
    {
        for(long j = 0; j < 10-i-1; j++)
        {
            if (vecPtr[j] > vecPtr[j+1])
            {
                temp        = vecPtr[j];
                vecPtr[j]     = vecPtr[j+1];
                vecPtr[j+1]   = temp;
                numExchanges++;
            }
            numComparisons++;
        }
    }
}

Answer 1

预计大约有 N²/2 次比较和交流。

特别是，内循环开始外循环的当前值。因此，在第一次迭代中，它遍历了整个数组。在后续的每次迭代中，它都会少遍历数组中的一项。

因此，内循环的迭代次数为 N + N-1 + N-2 ... 1。平均而言，这大约是 N/2。

如果你想更精确，还有一个细节需要考虑:内层循环从 i+1...N 开始迭代，所以它的最大值是 N-1 次迭代，而不是 N 次迭代。

因此，它不是精确的 N²/2，而是 N * (N-1)/2。在你的例子中，10*9/2 = 45。

这是比较次数的计数。对于掉期，您将获得其中的一定百分比，具体取决于无序商品的数量。在您的特定情况下，所有项目总是乱序的(因为您从相反的顺序开始)所以您为每次比较进行交换。对于任何其他顺序，您预计交换次数会减少。