c++ - 迭代冒泡排序

Question

我正在用 C++ 做一些关于排序算法的练习，但我无法理解其中一个。

它说实现一个函数，给定一个整数数组，应该使用冒泡排序算法(迭代)对它们进行排序，一旦 for 循环没有促进交换就应该终止的元素。这可能吗？

按照我的理解，终止算法的正常条件是排序等于 1。所以，在这个例子中，

void bubblesort( int v[], int size ) {
    for( int i = size; i > 0; --i )
        for( int j = 0; j < i; ++j ) {
            if( v[j] <= v[j+1] ) continue;
            int aux = v[j];
            v[j] = v[j+1];
            v[j+1] = aux;
         }
}

但这并不能解决这个问题，对吗？

Answer 1

根据我对您问题的了解，一旦内部 for 循环不执行任何交换，您就需要终止排序。这可以在 bool 的帮助下完成，如下所示:

void bubblesort(int v[], int size)
{
    bool flag;

    for (int i = size; i > 0; --i)
    {
        flag = true;

        for (int j = 0; j < i; ++j)
        {
            if (v[j] <= v[j + 1]) continue;

            flag = false;

            int aux = v[j];
            v[j] = v[j + 1];
            v[j + 1] = aux;
        }

        if (flag) break;
    }
}

说明:如果内部的if条件不满足，那么flag的值就会改变。如果对于每次迭代都满足 if，则 flag 的值不会改变，这将在外循环结束时进行检查。