迭代bubblesort

Question

我在c++上做了一些关于排序算法的练习，但是我无法理解其中的一个。

它说要实现一个函数，在给定一个整数数组的情况下，应该使用bubblesort算法(迭代)对它们进行排序，一旦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的值不会改变，这将在外部循环结束时进行检查。

Answer 2

不，考虑到你的解决方案并不能解决这个问题。

是的是可能的。

下面的代码包含修复它所需的所有更改。

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;
        }
    }
}