算法 - 冒泡排序算法及优化

怼烎@ 2023-06-03 05:51 26阅读 0赞

在面试过程中,经常会涉及到一些算法问题,下面说介绍一下冒泡排序算法及优化.

冒泡排序分为从大到小和从小到大两种排序方式,唯一区别在于两个数交换的条件不同,

从大到小排序是前面的数比后面的小时交换,而从小到大排序是前面的数比后面的数大的时候交换.

假设有N个数据放在数组nums中,现将数组nums中的N个数据从小到大进行排序

假设使用冒泡排序算法对5个整数**\{8，3，-2，7，6\}**进行从小到大的排序

**冒泡排序的基本思想:**

在a\[0\] 到a\[n-1\]的范围内,依次比较两个相邻元素的值,若a\[j\]>a\[j+1\] 则交换a\[j\] 和a\[j+1\]

否则不作交换, 直至完成最后一次循环比较.

![1261104-20190918170413200-208554341.png][]

如图可知：数组长度为n, 外层共循环n-1次, 外层循环增加一次 对应的内层循环就减少一次

外层循环控制比较的轮数, 内层循环控制的比较的次数

外层循环： for(int i=0; i<nums.length-1; i++)

内层循环： for(int j=0; j<nums.length-1-i; j++)

交换两个相邻元素的值：

int temp = nums\[j\];  
nums\[j\] = nums\[j+1\];  
nums\[j+1\] = temp;

**代码实现：**

![1261104-20190919094312165-675997056.png][]

运行效果：

![1261104-20190918172414232-1685996424.png][]

**冒泡排序算法优化：**

回顾一下刚刚描述的排序细节,仍以8，3，-2，7，6这个数组为例

![1261104-20190919100550047-1201605693.png][]

经过第二轮排序后,整个数组已经是有序的了,但是我们的排序算法仍然继续执行第三轮,第四轮

这种情况下,如果我们能判断出数组已经有序,并作出标记,剩下的几轮排序就可以不执行了,提前结束工作.

**代码实现:**

![1261104-20190919104121154-1448735972.png][]

运行效果:

![1261104-20190919102722261-1338768326.png][]

除此之外,我们还可以进一步优化冒泡排序算法.

假设使用冒泡排序算法对数组\{ **4, 3, 5, 6, 7**\} 按照从小到大顺序进行排序,那么我们应该如何对此进行优化呢？

**分析：**

该数组的特点是前半部分\{ **4，3**\}无序,后半部分\{ **5, 6, 7**\} 升序,并且后半部分的元素值已经是数组最大值

按照冒泡排序的思路进行排序

第一轮

元素4和3比较, 发现4大于3 所以4和3交换位置

元素4和5比较, 发现4小于5 所以4和5的位置不变

元素5和6比较, 发现5小于6 所以5和6的位置不变

元素6和7比较, 发现6小于7 所以6和7的位置不变

第一轮结束, 数组有序区包含元素值7

![1261104-20190919110838296-1341683144.png][]

第二轮

元素3和4比较, 发现3小于4 所以3和4的位置不变

元素4和5比较, 发现4小于5 所以4和5的位置不变

元素5和6比较, 发现5小于6 所以5和6的位置不变

第二轮结束,数组有序区包含元素值6

![1261104-20190919111158439-927629962.png][]

其实数组中后半部分元素值已经是有序的了, 可是每一轮还是需要比较很多次

如果能对数组中有序区进行界定,那么每一轮中在有序区的元素值就可以不用再比较了,这样就可以进一步

提高冒泡排序算法的性能.

我们可以在每一轮排序的最后,记录下最后一次元素交换的位置,这个位置也就是无序数组的边界,之后的就是

有序区了.

**代码实现:**

**![1261104-20190919114312734-717621643.png][]**

![1261104-20190919114355581-1298888385.png][]

运行效果

![1261104-20190919120231522-1735001886.png][]

转载于:https://www.cnblogs.com/54tester/p/11540731.html

[1261104-20190918170413200-208554341.png]: /images/20230601/d84aa1a0da3c4f78a259888762708b5d.png
[1261104-20190919094312165-675997056.png]: /images/20230601/ae9a2ee185094743a4982eca22cda9c0.png
[1261104-20190918172414232-1685996424.png]: /images/20230601/e48a54cfd1cd40ffb1d111f752762b19.png
[1261104-20190919100550047-1201605693.png]: /images/20230601/7b884d9407984b66ba3228a4f2130fad.png
[1261104-20190919104121154-1448735972.png]: /images/20230601/e7aa59fa9d8d45cfa38ad92077d635d6.png
[1261104-20190919102722261-1338768326.png]: /images/20230601/840f70b6cdfc44eaa7675c99bc6b3737.png
[1261104-20190919110838296-1341683144.png]: /images/20230601/8b76d4eef1da4ab6b81250e3116d623d.png
[1261104-20190919111158439-927629962.png]: /images/20230601/583d72e5320042a9a0b78d5768f3d8db.png
[1261104-20190919114312734-717621643.png]: /images/20230601/ea8a0eb2811c4c5d90db63a9c7778881.png
[1261104-20190919114355581-1298888385.png]: /images/20230601/c61c0fa8f09f41d9b82fc12dd6f8a423.png
[1261104-20190919120231522-1735001886.png]: /images/20230601/4c8d35dfd0824f439a88d6ea94bd8e5e.png