经典排序算法,冒泡排序的一点笔记。
冒泡排序(Bubble Sort)
冒泡排序是一种简单的排序算法。它适合小规模数据的排序,并且其效率比较低,但是作为一个入门的算法,还是值得学习的。
1. 冒泡排序思想
- 基本思想: 冒泡排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来,假设从小到大,即为较大的数慢慢往后排,较小的数慢慢往前排。
- 直观表达,每一趟遍历,将一个最大的数移到序列末尾。
2.算法描述(由小到大为例)
- 比较相邻的两个数,如果第一个数比第二个数大,则两数交换。
- 对之后的相邻元素进行同样的工作,从开始到最后一对,这样进行一次排序后,数据的最后一位会是最大值 ,第一次循环进行的次数为 arr.length-1。
- 之后对所有的元素重复以上的步骤,且以后每次循环的次数为arr.length-1-i (i为循环第几次 ,i 从零开始);
- 重复上述步骤,直到排序完成
动图演示:(图片来源参考资料)
3.代码实现
1 |
|
在上面的代码中我们会发现存在一些问题,就是明明数组已经有序了,但在循环中还是会进行对比,这样会增加执行的次数。这是我们可以优化的地方。
优化方法:就是设置一个标记位flag,如果已经排序了那么设置为false;如果不是有序的,那么设置为true。现在我们来看看优化后的代码。
1 |
|
其实这个原理很简单,利用flag做标记。如果在本轮排序中,元素有交换,则说明数列无序,如果没有交换,则说明数列已然有序,直接break。
本文采用CC-BY-SA-3.0协议,转载请注明出处
作者: Lee
作者: Lee