问题标题: 酷町堂：冒泡排序是什么

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有元素再需要交换，也就是说该数列已经排序完成。
       这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

（12比上面的数都小，经过多次与相邻数字交换，最后浮到了顶端）

如果我们要将下面的数从大到小排序，冒泡排序的过程是这样的
原序列：12 35 99 18 76

第一轮（从第一个数开始，相邻数字相比较、交换）：
12 35 99 18 76
35 12 99 18 76
35 99 12 18 76
35 99 18 12 76
35 99 18 76 12
此时末尾确定了最小的数 12

第二轮（还是从第1个数开始，相邻数字相比较、交换）：
35 99 18 76 12
99 35 18 76 12 （这里是35和18进行比较，不需要交换位置，18比35小）
99 35 18 76 12
99 35 76 18 12 （最后一位的12是确定的，不需要比较）
第二轮在末尾确定了第2小的数 18

第三轮：
99 35 76 18 12
99 35 76 18 12
99 76 35 18 12
第三轮在末尾确定了第3小的数 35

第四轮：
99 76 35 18 12
99 76 35 18 12

这里对于5个数，需要4轮排序，每轮确定第i小的数。
每轮比较的数字对数比上一轮少一对。

代码实现冒泡排序（将a数组中a[1]~a[n]的元素从小到大排序）

for(int i=1;i<=n-1;i++)//表示排序的轮数，共需n-1轮 for(int j=1;j<=n-i;j++)//第i轮要确定第i大的数，放在后面，需要比较n-i对数字（因为后面i-1个数已经确定下来，不需要比较） if(a[j]>a[j+1]) //相邻的数字比较，如果前大后小，就需要交换位置 swap(a[j],a[j+1]);

二、冒泡排序优化

下面是一个大小为6的数组，经过一轮冒泡排序就是有序的了。

第一轮中，46分别与20、33、38、43比较并交换了位置，与60比较后不交换位置，此时数组中元素20,33,38,43,46,60已经是有序的了，后面就没必要再继续进行排序。

冒泡排序优化的原理：基本冒泡排序算法的代码**进行了n-1轮冒泡排序。但实际上当某一轮排序过后序列已有序时，显然不需要再继续排序，排序轮数可能远小于n-1轮。

冒泡排序优化的代码实现

for(int i=1;i<=n-1;i++) { bool flag=false; //定义一个标志位，用来记录某轮排序是否有数据交换发生 for(int j=1;j<=n-i;j++) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); flag=true; //有数据交换，则改变标志位的值 } } if(flag==false) //如果标志位的值没改变，说明本轮排序没有数据交换，即数组本身已经有序了，那么退出循环 break; }