用python实现冒泡算法,五分钟彻底了解冒泡算法

鲁迅说过:“十年以后,不懂编程的人,是新世纪文盲。”,没错是鲁迅说的,不信看下面聊天记录。

好了,现在大家都知道学会编程的重要性了,编程无非就是使用计算机语言实现机器代替人为计算。计算机语言使用的逻辑抽象出来就是算法。所以算法是非常重要的。

现在大家也知道算法的重要性,接来下,就让我们进入今天的主题《冒泡算法》,什么是冒泡算法呢?就是像我这种消失了很久,然后突然出来发篇文章刷下存在感的行为就是俗称“冒泡”。那冒泡算法就是用来计算我什么时候该出现的吗?当然不是。好了,不扯了,不然你们要关闭这篇文章了。实际上冒泡算法的定义是这样的:“冒泡算法一般是指冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢浮到数列的顶端,故名冒泡排序”。

是不是表示看不懂?看不懂就对了,不然关注我有什么用。为了让大家快速了解,我举个栗子,等大家明白了,我就把吃掉。

有这样一组数列:

[7,6,5,4,3,9,8,2,1],

我们想排序成这样:

[1,2,3,4,5,6,7,8,9]。

要怎么做呢?第一次,我们可以把9排到最右边。

最终结果就变成这样:

[6, 5, 4, 3, 7, 8, 2, 1,9],

然后第二次,再把8拍到倒数第2位,最终结果就变成:

[5, 4, 3, 6, 7, 2, 1,8, 9],

以此类推,排列8次以后就完成了。是不是很简单,很像在冒泡啊?

细心的你会发现第一次试除了9的位置有变化,其它数据的位置也都变了。

原始数据 :

[7,6,5,4,3,9,8,2,1]

第一次排序以后变成 :

[6,5,4,3,7,8,2,1,9]

而不是1和9换位置如这样:

[7,6,5,4,3,1,8,2,9]

这是为啥呢?因为冒泡算法的第一次的实现过程,为了方便理解暂且称为子过程吧,子过程实际上是这样的:

[7, 6,5, 4, 3, 9, 8, 2, 1]

解释:第一次,从第一个数开始和右边的数字比较,如果左边的数比右边的数字大,就左右互换,第一次6和7比较,7大,然后6和7交换位置。

[6,7, 5,4, 3, 9, 8, 2,1]

解释:第二次,第一个数字比较完后,就接着第二个数字和第三个数字比较,如果左边的数比右边的数字大,就左右互换。

依次类推如下,最终完成了9到最右边:

[6, 5,7, 4,3, 9, 8, 2, 1]

[6, 5, 4,7, 3,9, 8, 2, 1]

[6, 5, 4, 3,7, 9,8, 2, 1]

[6, 5, 4, 3, 7,8, 9,2, 1]

[6, 5, 4, 3, 7, 8,2, 9,1]

[6, 5, 4, 3, 7, 8, 2,1, 9]

所以第一遍大循环把9排到最右边实际上是交换了很多次的。逻辑整理清楚了,接下来抽象成编程语言就很简单了。

Python实现方式如下:

到这里是不是就完美了呢?如果觉得是,你就太年轻了。

如果原始数据是[1,2,3,4,5,7,9,8],其实跑过一次循环就可以达到我们想要的方式,但按上面的代码实现方式,无论如何都都要跑8次大循环,n次子过程。

这样很不科学,所以就有了以下的优化方式,但我们发现子过程,一次都不需要交换的时候,就说明已经排序好了。于是优化的代码如下:

到这里是不是就完美了呢?

是的,只能这样了。所以本文结束。

本文纯属原创,如有错漏,敬请指出!

微信公众号:艾伦未来

有什么问题也可以给我留言哦。还有别忘了点赞和转发哦!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180603G0PLOA00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券