冒泡排序法需要两次扫描，所以从时间复杂度来说，是O(n2).
如果用图形表示，是这样的：
但是我们可以加以改进。
首先是，如果在排序中间，整个向量已经达到了有序状态，可以直接跳出来。
这样它的复杂度由一个三角形变为一个梯形。
同时，可能存在部分有序的状态，所以可以再次改进：
深蓝色为可能占用的时间复杂度。
我自己写了一个代码测试了一下：
#include<iostream> #include<vector> #include <algorithm>//question1: 使用swap()需要使用这个头文件
//函数模板 using namespace std; template <typename T1> T1 bubble(T1 lo, T1 hi,int *x) { T1 last=lo; while(++lo<hi) if(x[lo-1]>x[lo]) { last=lo; swap(x[lo-1],x[lo]); } return last; } template <typename T1> void MySort(int*x, T1 lo, T1 hi ) { while(lo<(hi=bubble(lo, hi, x))); } int main(void) { //int x=0; //cout<<"the result is "<<x<<endl; int p[7]={1,3,5,2,1,7,2}; int low=0; int high=7; MySort(p,low,high); for(int i=0;i<7;i++) cout<<"the result is "<<p[i]<<endl; return 0; }
原文：https://www.cnblogs.com/fantianliang/p/11728612.html