当前位置：网站首页 > 技术资源 > 正文

排序算法(1):5分钟理解冒泡排序算法并用Python实现

off999 2024-12-26 15:54 18 浏览 0 评论

【上期我们刚掌握算法复杂度，这期讲到的冒泡排序算法，它的算法复杂度是怎样的呢？如何简单理解其原理并用代码实现呢？让我们一起用5分钟时间看看吧！】

冒泡排序算法

一、算法原理

冒泡排序(Bubble Sort)是一种常见的排序算法，它需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。先来看一张gif动图：

可能看动图很多人都已经能理解了，如果感觉一下get不到也没关系，在第二部分还会放具体的步骤，更直观清晰。

二、步骤拆解

以列表 [1, 7, 3, 9 2] 进行升序排列为例，列表的初始状态如下图：

1. 从列表的开头，比较相邻的两个元素，如果第一个值比第二个值大则交换。1于7则不需要交换：

2. 向列表的结尾方向“走访”，比较第二组相邻的元素(第二个和第三个)。因7大于3则进行交换：

3. 继续“走访”，比较第三组相邻的元素(第三个和第四个)。7小于9则不需要交换：

4. 继续“走访”，比较第四组相邻的元素(第四个和第五个)。因9大于2则进行交换：

5个数据经过4步，找出了5个数据中的最大值置于最末端，这就是第一轮冒泡；在下一轮“冒泡”中，不需要再将9进行比较，所以需要比较的数据为4个，可以3步找出4个数据中的最大值，依此类推……最终得到排序结果如下：

三、代码实现

可以看到上述过程是不断的循环，因此能想象代码中大概率需要用到for循环，故冒泡排序算法（升序）的Python代码如下：

运行结果为：

怎么样，是不是感觉很简单？留一个小思考题：可以想想冒泡排序的算法复杂度，包括时间复杂度和空间复杂度分别是多少，下期也会放答案。

【今天就讲到这里，每天进步一点点，足矣】

相关推荐