c++ - Bubblesort 让我抓狂

Question

这是一个非常简单的问题。我用冒泡排序代码在线查看，看起来我也在做同样的事情。这是我带有模板的完整 C++ 代码。但是输出有点奇怪!

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        for(int j=0; j<i-1; j++){
            if(a[j+1]>a[j]){
                cout<<"Yes at j="<<j<<endl;
                T temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

int main(){
    int a[] = {1,2,6,3,4,9,8,10};
    sort<int>(a,8);
    for(int i = 0; i<8; i++){
        cout<<a[i]<<endl;
    }
    return 0;
}

输出:

但是当我稍微更改逻辑以尝试按升序对其进行排序时。即，更改为:if(a[j+1]<a[j]) , 输出没问题!

我哪里做错了？

提前致谢!

Answer 1

您的代码的问题是您试图将内容往下冒泡，但向上循环。如果你想把东西往下冒泡，你需要向下循环，这样一个需要下降的元素就会下降到它需要的程度。否则，对于 i 的每次迭代，您只知道一个元素可能冒出一个空格。

同样，如果你向上冒泡，你也需要向上循环。

如果你想看看会发生什么，下面是你的代码和一些输出语句，这样你就可以了解发生了什么:

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        cout << "i: " << i << endl;
        for(int j=0; j<i-1; j++){
            if(a[j+1]>a[j]){
                cout << "\t Yes at j = " << j << endl;
                T temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;

                for(int k = 0; k < size; k++) {
                    cout << "\t a[" << k << "]: " << a[k] << endl;
                }

                cout << endl;
            }
        }

        cout << "\n" << endl;
    }
}

int main(){
    int a[] = {1,2,6,3,4,9,8,10};

    cout << "initially:" << endl;
    for(int k = 0; k < 8; k++) {
        cout << "a[" << k << "]: " << a[k] << endl;
    }

    cout << "\n" << endl;

    sort<int>(a,8);
    cout << "\n sorted:" << endl;
    for(int i = 0; i<8; i++){
        cout << a[i] << endl;
    }
    return 0;
}

如果您运行此程序，您会发现对于具有较高索引的条目，没有足够的迭代次数来将它们一路冒泡到它们需要去的地方。

此外，这里是固定了向下冒泡的代码(即按相反顺序排序):

#include <iostream>

using namespace std;

template <class T>
void sort(T a[], int size){
    for(int i=0; i<size; i++){
        cout << "i: " << i << endl;
        for(int j=size - 1; j>i; j--){
            if(a[j-1]<a[j]){
                cout << "\t Yes at j = " << j << endl;
                T temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
}

int main(){
    int a[] = {1,2,3,4,5,6,8,10};
    sort<int>(a,8);
    cout << "\n sorted:" << endl;
    for(int i = 0; i<8; i++){
        cout << a[i] << endl;
    }
    return 0;
}