博客

时间复杂度：

最好O(n)：基本有序

最差O(n2)：基本逆序

#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        bool flag = true;
        for (int j = vec.size()-1; j > i; j--) {
            if (vec[j-1] > vec[j]) {
                swap(vec[j-1], vec[j]);
                flag = false;
            }
        }
        if (flag == true) {
            return;
        }
    }
}

int main(int argc, char* argv[]) {
    vector<int> vec = {2, 1, 5, 3, 5, 4};
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;
    BubbleSort(vec);
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;
    return 0;
}