图解冒泡排序，让你学习效率事半功倍

柔情只为你懂 2024-04-03 13:56 90阅读 0赞

冒泡排序是一个比较经典和简单的排序算法，今天我们从算法本身，时间复杂度以及稳定性方面来看看冒泡排序，这些方面也是研究其他排序算法的一般思路！(划重点，认真听呦！本文篇幅很长，但是用简单的故事带你了解冒泡排序，便于理解！)

冒泡思想

在算法过年，相传有一位算法大师，他不喜欢做官，一心只在民间传道受业，弟子三千，人称“江湖巍哥”。

有一天，江湖巍哥带着新收的弟子张大胖去溪边游玩，看到许多大大小小的石头在溪边，他灵机一动，就拿起了四个大小不同的石子，摆成一行：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍][d2c19a1fcef11990398f6719186901fd.jpeg]

巍哥问：“大胖，你如何将这些石子按照从小到大的顺序从左到右依次排列成一行？”

“先找出最大的放在右边，然后再找出次大的，放在最大的左边，按照这个规律就可以依次排好了”，大胖不假思索地回答道

“那你如何找到最大的呢？”

“用肉眼看”，大胖弱弱地说了一句。

“蠢材，怎么可以用肉眼看，如果成千上万你也用肉眼看吗？咱们算法国以算法著称，就是让一切问题的解决都可以最终化为一个算法，可以用程序写出来！”巍哥严厉地批评道。

“那该如何找最大的呢？” 大胖问道

“你看那水中的鱼，他们时不时地吐出泡泡，那泡泡越往上走就会越大，我们可以借鉴这种思路啊。”

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_02][02]

“从第一个石子开始，让它和右边相邻的石子进行比较，如果左边的石子大于右边的石子，那么就交换两个石子的位置，(也可以左小于右交换，这里采用大于交换)，这样每比较一次，大的就跑到右边，直到跑到最右边”，巍哥说道。

巍哥看大胖不明白，解释道：“起始时，左下标指向第一个石子，右下标指向第二个石子，然后比较”，说着说着画了一个图

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_03][03]

“然后左右下标同时向右移动，再次比较”，巍哥接着说道，手不停的画着

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_04][04]

“这样一来，每次比较完，右下标指向的石头就是已经比较过的元素中的最大元素”，巍哥微微笑了一下，然后又画了一个图：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_05][05]

“按照这个做法，这一趟下来所有石子中最大的就跑到最右边了”，大胖悟出了其中的真谛，接着老师的话说了一句，自己在地上也画了一个图：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_06][06]

“这是第一趟排序，经过这趟排序之后，最大的就在最右边了，也就是排好序了，那么接下来就从剩下的三个石子中选最大的了，规则就和上面的一样了”，大胖继续说道，并画了一个图：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_07][07]

巍哥脸上露出满意的笑容。接着问道：“如果有 N 个石子，称从左到右找最大为一趟，那么要排好序需要多少趟？”

大胖想了想，说道：“需要N-1次，因为如果因为N-1个数都排好了，那么最后一个数也就不用排了”，顺便画了一个图演示刚才四个石子的情况

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_08][08]

冒泡代码

“那你能把这个过程用代码实现吗？”，巍哥问道。

“这个......”，大胖挠了挠头，傻傻地笑了一下，巍哥不满地看了新徒弟一眼，只好自己写了，只见他飞速地写了短短的几行代码：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_09][09]

大胖心中暗暗惊叹老师的功力。

“这个第一层循环是控制趟数，第二行能具体讲讲吗？”，大胖再次挠了挠头。

“第二层就是控制你第 i+1趟(因为i从0开始)所比较的次数，第 i +1 趟比较了 n - 1 -i 次”，巍哥说道，最后画了两张图。

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_10][10]

“随着趟数的增加，比较的次数也随之减小，这个规律很容易发现吧！”，巍哥说道。

张大胖点了点头，明白了。

时间复杂度

“那你说说这个算法的时间复杂度吧。”，巍哥问道。

张大胖心说好不容易跟着老师出来一次，本想游山玩水，没想到这么多问题！ 他不敢怠慢，赶紧盘算起来：

4个石子，排序完需要3趟，第一趟需要比较3次，第二趟需要比较2次，第三趟需要比较1次，那一共比较了 3 + 2 + 1 次。

那推广到数量为 n 的规模的话，那就需要 (n-1) + (n-2) +...+2+1 次，这不就是一个等差数列吗，很显然：

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_11][11]

根据复杂度的规则，去掉低阶项(也就是n/2),并去掉常数系数，那复杂度就是O(n^2)了

“O(n^2)”,大胖想了一会说道。

“恩恩，不错，孺子可教。” 巍哥赞赏到，心想这小子数学还不错。

稳定性

“那这个算法稳不稳定呢？”，巍哥又问道。

“哦? 什么是稳定性？”

奥，这个还没有给他讲过，巍哥忽然想起来。

“所谓稳定性，其实就是说，当你原来待排的元素中间有相同的元素，在没有排序之前它们之间有先后顺序，在排完后它们之间的先后顺序不变，我们就称这个算法是稳定的”，巍哥说道，顺便画了一个图举了一个例子

![图解冒泡排序，让你学习效率事半功倍\_图解冒泡排序，让你学习效率事半功倍\_12][12]

“看到了吧，原本同样大的石子，蓝色的在绿色的左边，拍完序后蓝色的仍然在绿色的左边，这就是稳定的”，巍哥解释道。

“哦，我懂了，那冒泡排序就是一个稳定的排序了，因为在交换的时候，如果两个石子相同，那么就不交换\[if (arr\[j\] arr\[j+1\])\{ 交换\}\],相同元素不会因为算法中哪条语句相互交换位置的。”

“恩，对的”，

天色渐晚，巍哥和弟子准备回去，张大胖问道：“老师，这个排序算法是不是叫做冒泡排序？”

巍哥说：“没错，很形象吧？对了大胖，我今天发现你的理论基础不错，一点就透，但是编码功底太差，以后要多加练习啊，不要成为一个眼高手低的人啊。”

“谨遵老师教诲！我一定多加练习！

举报/反馈

[d2c19a1fcef11990398f6719186901fd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/34a4ae4ca95f42aca27cfa87010ab013.jpeg
[02]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/039a26a22c7646d9999c31f31fe8cfc5.jpeg
[03]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/301c86d776804485bf0d827d5bbc140c.jpeg
[04]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8e1cb90c61464251a5f479eb6e9183c2.jpeg
[05]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d97e966f84a54f6db16618854bd85480.jpeg
[06]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f302fe9909b9423caa589fc7d60cc027.jpeg
[07]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/f968657d0e744a6a8367bda7457a9f37.jpeg
[08]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/30dee5c1d11b40eb90296ca66e477bd0.jpeg
[09]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0a9fb090bc8142b29884a2e2785870f0.jpeg
[10]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/59e60f869e8246dca7833f2fa0889ebc.jpeg
[11]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/529e594dbdcc4c08a04dcf768d821e90.jpeg
[12]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e1ec3a4d06e14231a7757a3a1a05ac6f.jpeg