华师一附中OI组

标题: 冒泡排序 [打印本页]
作者: admin    时间: 2020-7-17 14:36
标题: 冒泡排序
冒泡排序是一种比较快速的简单排序方法，他通过比较和交换相邻的两个数来达到排序的目的。
假设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    时间: 2020-7-17 14:48
这里大家看得到，每轮比较得时候都有比较，有时会有交换，但是感觉交换的次数越来越少，因为小的慢慢沉到了右边，当某一轮比较时候没有交换，说明所有的数都比他左边的那个小，是不是就说明已经排好序了呢？
这是冒泡排序比较好的地方，不需要做满循环，可以提前结束，设置一个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.                 }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2