基本思想：两个数比较大小，较大的数下沉，较小的数冒起来
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> arr{ 3,34,4,12,5,2}; cout << "原数组:" << endl; print(arr); //冒泡排序 for (int i = 0; i < arr.size(); i++) { //表示趟数 for (int j = arr.size() - 1; j >i ; j--) { if (arr[j - 1] > arr[j]) { swap(arr[j], arr[j - 1]); } } } cout << "排序后：" << endl; print(arr); system("pause"); }平均时间复杂度：O(n2)
优化：
针对问题： 数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案： 设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
#include<iostream> #include<vector> using namespace std; void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } int main() { vector<int> arr{ 3,34,4,12,5,2}; cout << "原数组:" << endl; print(arr); //冒泡排序优化 bool flag; for (int i = 0; i < arr.size(); i++) { //表示趟数 flag = false; for (int j = arr.size() - 1; j >i ; j--) { if (arr[j - 1] > arr[j]) { swap(arr[j], arr[j - 1]); flag = true; } if(!flag) break; } } cout << "排序后：" << endl; print(arr); system("pause"); }时间复复杂度：最好的情况本身就是有序的，比较次数，就是n-1次的比较，没有数据交换是，时间复杂度为O(n)；最坏的情况：即待排序表示逆序的情况需要比较次，并作等数量级的记录移动，因此，总的时间复杂度为O（n方）
