迭代冒泡排序

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

否，根据描述，您的解决方案无法解决任务。
是的，这是可能的。
以下代码包含修复它所需的所有更改。

void bubblesort( int v[], int size ) {  
    boolean change; //create a boolean to track if the current iteration changed anything 
    for( int i = size-1; i >= 0; --i ){  
        change = false; //at the start of each iteration set it to false
        for( int j = 0; j < i; ++j ) {  
            if( v[j] <= v[j+1] ) continue;  
            change = true; // if something changed set it to true  
            int aux = v[j];  
            v[j] = v[j+1];  
            v[j+1] = aux;  
        }  
        if(!change){ // when it's still false at the end of the itteration you are done
            return;
        }
    }
}

Answer 2

从我了解到的你的问题来看，一旦内部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 的值不会改变，这将在外循环结束时进行检查。

迭代冒泡排序

Iterative bubblesort

c++

bubble-sort