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