今天我们来学习一种新的排序方法——冒泡排序。

上一次我们学习了一种简单的排序——计数排序,这种排序有两个局限: 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 <iostream> #include <cmath> using 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]<a[j-1]) //从后面往前两两判断 {
swap(a[j],a[j-1]); //交换 t=0; } if (t) break; //如一次循环中没有交换,说明已经排好序了,退出循环 } for
(i=1;i<=n;i++) cout <<a[i] <<" "; //输出 return 0; //华丽结束 }
冒泡排序时间复杂度为O(n²),比计数排序要慢,但没有数据类型和范围的局限(当然,范围不能太大),是一种很好用的稳定排序。

冒泡排序讲解完毕,下期预告:排序的稳定性。

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信