今天我们来学习一种新的排序方法——冒泡排序。
上一次我们学习了一种简单的排序——计数排序，这种排序有两个局限： 1、要排序的类型必须是有序类型（如整形），像浮点型这种无序数据类型则不能用计数排序。 2、要排序的数据必须有固定的小范围，否则就会数组太大爆内存。
针对这种缺点，人们研发了冒泡排序（从小到大）：从后面开始往前两两对比，如果前数大于后数则交换，否则不交换，重复此操作，直到在一次操作中没有交换才结束。由于在过程中，最小/大数会不断向前移动，像泡泡从水里冒出来一样，故称冒泡排序。
文字看不懂，看看具体操作：将数列：4 9 2 8 6 从小到大排序。
第一步： 4 9 2 6 8 // 后面两个数 8 6 比较，8大于6，所以交换。
第二步： 4 9 2 6 8 // 接下来将 2 6 比较，不交换。
第三步： 4 2 9 6 8 // 将 9 2 比较，交换。
第四步： 2 4 9 6 8 // 将 4 2 比较，交换。
//现在完成了最小数放在最前面，用了4次比较，3次交换。我们要将第2小数放到第2位。
第五步： 2 4 9 6 8 // 再次从后面开始，6 8 比较，不交换。
第六步： 2 4 6 9 8 // 将 6 9 比较，交换。
第七步： 2 4 6 9 8 // 将 4 6 比较，不交换。
//我们已经将第2小数放到第2位，用了3次比较，1次交换。现在要将第3小数放到第3位。
第八步： 2 4 6 8 9 // 将 9 8 比较，交换。这时，排序已经完成，但程序还没结束。
第九步： 2 4 6 8 9 // 将 6 8 比较，不交换。
//我们已经将第3小数放到第3位，用了2次比较，1次交换。现在要将第4小数放到第4位。
第十步： 2 4 6 8 9 // 将 8 9 比较，不交换。
这时，程序结束了。我们也将数列排好了。每一次的交换如下：
4 9 2 8 6
4 9 2 6 8
4 2 9 6 8
2 4 9 6 8
2 4 6 9 8
2 4 6 8 9
排序结束。
知道了基本原理，代码也就好打了（将整形的数从小到大排序）：
#include#includeusing namespace std;
int n,i,j,a[2000];
bool t; //定义变量
int main()
{
cin >>n;
for (i=1;i<=n;i++)
cin >>a[i]; //输入
for (i=1;i<=n;i++)
{
t=1;
for (j=n;j>i;j--)
if (a[j] 冒泡排序时间复杂度为O（n²），比计数排序要慢，但没有数据类型和范围的局限（当然，范围不能太大），是一种很好用的稳定排序。
冒泡排序讲解完毕，下期预告：排序的稳定性。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧