冒泡排序

admin

冒泡排序是一种比较快速的简单排序方法，他通过比较和交换相邻的两个数来达到排序的目的。
假设10个数分别是7,5,6,4,8,2,3,5,9,1，想要由大到小排列
1、比较第一二两个数7和5,7比5大，不用换
2、比较第二三两个数5和6,5比6小，要交换，序列变成了7,6,5,4,8,2,3,5,9,1
3、比较第三四两个数5和4,不动
4、比较第四五两个数4和8,要交换，序列变成了7,6,5,8,4,2,3,5,9,1
5、比较第五六两个数4和2,不动
6、比较第六七两个数2和3,要交换，序列变成了7,6,5,8,4,3,2,5,9,1
7、比较第七八两个数2和5,要交换，序列变成了7,6,5,8,4,3,5,2,9,1
8、比较第八九两个数2和9,要交换，序列变成了7,6,5,8,4,3,5,9,2,1
9、比较第九十两个数2和1,不动
一轮比较和交换后，最小的数字1，到达了第十位，前面的在排序就可以不考虑它了。
第二轮开始：序列初始是7,6,5,8,4,3,5,9,2,1
1、比较第一二两个数7和6,不动
2、比较第二三两个数6和5,不动
3、比较第三四两个数5和8,要交换，序列变成7,6,8,5,4,3,5,9,2,1
****  
8、比较第八九两个数3和3,不动，序列变成7,6,8,5,4,5,9,3,2,1
这样8次之后，2到达了目标位，下面只要考虑前7个数了。

每次是ai和ai+1两个比较，那么第一轮i的范围是1-9，第二轮i的范围是1-8,第九轮
内层循环写作 ：
for(j=1;j<=i;j++) if (aj<aj+1) swap
外层循环枚举i的值，写作for (i=9;i>=1;i--)
套在一起就是：

1. #include <iostream>
   
2. using namespace std;
   
3. int a[11]= {0,7,5,6,4,8,2,3,5,9,1};
   
4. int main()
   
5. {
   
6.         for (int i=9; i>=1; i--) ///i控制内层循环的尾部
   
7.                 for (int j=1; j<=i; j++)
   
8.                         if (a[j]<a[j+1])  swap(a[j],a[j+1]);
   
9.         for (int i=1; i<=10; i++) cout<<a[i]<<' ';
   
10.         return 0;
    
11. }
    

复制代码

admin

这里大家看得到，每轮比较得时候都有比较，有时会有交换，但是感觉交换的次数越来越少，因为小的慢慢沉到了右边，当某一轮比较时候没有交换，说明所有的数都比他左边的那个小，是不是就说明已经排好序了呢？
这是冒泡排序比较好的地方，不需要做满循环，可以提前结束，设置一个b标记，初值为1，当一轮比较时有交换，b=0,若一轮比较后，b=1，以后的不用做了。

1. bool b=1;
   
2.         for (int i=9; i>=1 && b==1; i--) ///i控制内层循环的尾部
   
3.                 {
   
4.                         b=1;///标记初值
   
5.                         for (int j=1; j<=i; j++)
   
6.                                 if (a[j]<a[j+1])
   
7.                                         {
   
8.                                                 swap(a[j],a[j+1]);
   
9.                                                 b=0;///有交换
   
10.                                         }
    
11.                 }

复制代码