//冒泡排序

include[HTML_REMOVED]

using namespace std;

void bubblesort(int data[],int n){
int flag=0;//一定记住冒泡有个flag标志
for(int i=1;i[HTML_REMOVED]data[j+1]){
int temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
flag=1;
}
}
if(flag==0) break;
}
}

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
bubblesort(data,10);
cout<<endl;
for(int i=1;i<=10;i)
cout<<data[i]<<’ ‘;
}

//分析
//最好情况，有序，那么比较一遍没有发生交换，直接退出 On
//最坏情况，逆序，比较最多，交换最多，n-1,n-2,…1 On²
//有了flag，排序趟数是和初始有关的

//稳定，if(data[j]>data[j+1])
//这里每次都可以确定一个元素的最终位置
//思考一下昨天写的插入类，插入最后一个元素，都可能导致其余元素全部移动
//所以只能确定前面部分有序，直到最终才能得到完整有序

//顺序表和链表均可以，冒泡还可以作为验证有序的方法