排序算法之冒泡排序及其优化

淩亂°似流年 2024-04-03 13:59 118阅读 0赞

冒泡排序

思想

比较相邻两个元素，如果前面的元素比后面的元素大，则交换位置。最后一个元素必定会是最大值。

排除掉最后一位元素，继续循环，直至没有元素需要比较

可以看出，冒牌排序其实和选择排序时很像的，只不过选择排序是比较数据，先记录下最小/大值的下标，等一趟循环结束的时候再交换位置；

而冒泡排序在比较数据的同时也做了交换。

性能

时间复杂度与选择排序一样，时间复杂度为O(n^2)。

由于它们的比较次数一样，而冒泡排序的交换次数多，所以一般冒泡排序会比选择排序慢。

但冒泡排序有一个优势，那就是每经过一次循环，数组的有序性就会变高。我们可以利用这点来优化冒泡排序，优化方法请看下文。

代码

普通冒泡排序的Python代码：

![排序算法之冒泡排序及其优化\_排序算法之冒泡排序及其优化][f665b6ac6146ed43c5ac26412b62cdff.jpeg]

优化

优化一

我们会发现如果数组一开始就是有序的或者再经过前几次循环的时候就已经变得有序了，但上述程序还是会继续循环比较。针对这一点我们可以进行一次优化：

![排序算法之冒泡排序及其优化\_排序算法之冒泡排序及其优化\_02][02]

经过优化之后，最好的情况下，时间复杂度为O(n)。

优化二

优化一针对的是整个数组已经有序的情况。那如果一个数组，假设有一万个数据，其实从一开始或者几次循环之后，后5千个数据已经是有序的且比前5千个数据要大，

在上述代码中，每次循环仍然会循环到上次循环找出的最大值的前一位。针对这一点，我们还可以再做一次优化：

![排序算法之冒泡排序及其优化\_排序算法之冒泡排序及其优化\_03][03]

优化三

假如还是刚才那个数组，后五千个数据已经有序，但最后一位是整个数组中的最小值，我们会发现优化二中的优化根本起不了作用。那想要让优化二起作用，那么就需要把那个最小值拿到前面来，有什么办法呢？很简单，就是来一次反向冒泡就行了。这样的算法被叫做双向冒泡排序(也叫鸡尾酒排序)，为了高雅地装逼，我们就叫它鸡尾酒排序吧。

![排序算法之冒泡排序及其优化\_排序算法之冒泡排序及其优化\_04][04]举报/反馈

[f665b6ac6146ed43c5ac26412b62cdff.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/85a8049c48a44eddba6a635a53c2421b.jpeg
[02]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3a5050a28ec149639d8941ae895adf94.jpeg
[03]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8a176d2cb4a04581b79f1231992093d9.jpeg
[04]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/95721fdbc21b4aba919ab8ad03b64ac5.jpeg