快速上手 C++ 数据结构与算法
王健伟
《C++ 新经典》系列作者,资深 C++ 讲师
3224 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 55 讲
结束语 (1讲)
快速上手 C++ 数据结构与算法
15
15
1.0x
00:00/00:00
登录|注册

35|冒泡排序:大数下沉,小数上浮

你好,我是王健伟。
前面我带你学习了插入类排序中的直接插入排序和希尔排序,这次,我们讲解另一类排序——交换类排序。
所谓交换类排序,就是根据序列中两个关键字的比较结果,来决定是否要交换这两个关键字对应的记录在序列中的位置。
交换类排序主要包括冒泡排序和快速排序,这在前面已经提到过。这节课,我先带你看一看冒泡排序。

冒泡排序基本概念

冒泡排序的英文名称是 Bubble Sort,也叫起泡排序。
按照从小到大排序来说,它的基本思想是在有 n 个元素的序列中,先将第一个记录的关键字和第二个记录的关键字进行比较,也就是两两比较相邻记录关键字,如果第一个记录的关键字大于第二个记录的关键字,则交换这两个记录。接着,比较第二个记录的关键字和第三个记录的关键字,如果第二个记录的关键字大于第三个记录的关键字,则交换这两个记录。依次类推,直到第 n-1 个记录和第 n 个记录比较完为止。
上述这些过程叫第一趟冒泡排序。这样做的结果就是将关键字最大的记录放到了最后一个记录位置上。显然,对于数组{16,1,45,23,99,2,18,67,42,10},第一趟冒泡排序后,结果为{1,16,23,45,2,18,67,42,10,99}。如图 1 所示:
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

冒泡排序是一种交换类排序算法,通过比较相邻记录的关键字大小来决定是否交换它们的位置。在冒泡排序中,大的数据会下沉,小的数据会上浮,类似气泡在水中上浮的过程,因此得名。冒泡排序的基本思想是通过多趟排序,将当前参与排序的数字中的最大数字下沉到最后,直到没有记录交换发生为止。文章详细介绍了冒泡排序的基本概念和实现代码,以及对冒泡排序算法进行改进以提升执行性能的方法。冒泡排序算法的实现简单易懂,是一种稳定的排序算法,但在待排序数据量较大时,排序速度会减慢,因此需要采用其他排序方法。文章还提出了两个思考题,分别是关于不同排序顺序的实现过程是否相同以及如何优化冒泡排序算法的时间复杂度。整体而言,本文通过简洁清晰的语言和实例代码,使读者能够快速了解冒泡排序算法的基本原理和实现方式,以及对其进行改进和优化的思考。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(1)

  • 最新
  • 精选
  • Bruder_Jin
    【思考题回答】 1、两种方式的区别就是两个数交换的条件不同,从大到小排序是前面的数比后面的小的时候交换,而从小到大排序是前面的数比后面的数大的时候交换 2、进一步优化冒泡排序算法的方法: 记录最后一次交换的索引,作为下一次冒泡的比较次数。 这样操作可以让某个数组中后面“大部分”已经有序的情况下,无需再比较额外的次数。 基于该篇文章给出来的代码,修改如下 //冒泡排序(从小到大) template<typename T> void BubbleSort(T myarray[], int length) { if (length <= 1) //不超过1个元素的数组,没必要排序 return; int num = length - 1; //外层循环只控制排序的趟数 while (true) { int last = 0; //最后一次交换索引问题 //内层循环控制元素的大小比较和交换位置 for (int j = 0; j < num; ++j) //每趟比较的次数都会减少 { if (myarray[j] > myarray[j + 1]) //前面的数据如果比后面的数据大 { //交换元素位置 T temp = myarray[j + 1]; myarray[j + 1] = myarray[j]; myarray[j] = temp; last = j; // 发生最后交换的索引 } } //end for j num = last; //最后交换的索引当做下次遍历时比较次数 if(num == 0) { // 没有发生交换,退出循环 break; } } return; }
    2023-06-08归属地:广东
    1
    1
收起评论
显示
设置
留言
1
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部