零基础学python 15 经典算法:冒泡排序法

avatar 2017年4月30日20:59:25 评论 1,932

上节课我们学习了循环的嵌套,而利用这个循环的嵌套我们就可以完成一个非常经典的算法:冒泡排序法。

什么是冒泡排序法呢?

冒泡排序法是用来给一系列数字进行从大到小或者从小到大排序的经典算法。因为每次遍历只能将一个数字归位,就像冒气泡一样,东冒一个西冒一个的,所以称作冒泡排序法。该算法在众多编程语言中的编程思想是一致的。


让我们举一个非常简单的例子来表达冒泡排序法的核心思想:

比如我们有一个list,[5, 4, 3, 2, 1],要求是请把这个list的元素从小到大进行排列。为了完整的展示我们的核心思想,我这里特意把这个例子list的默认状态从大到小排列。实际情况中,可能它们是乱序的,最大的不一定在最前面,也可能在中间。但是代码都一样的。

其实程序的算法思想和我们用人工来进行计算的思想是比较一致的。首先我们来思考一下我们如果是平常使用人工进行排序的时候是怎样的呢?很简单,要不就是每次找出最小的数把它放到最前面,要不就是找到最大的数放到最后面。这里我们使用后者的办法。

具体怎么做呢?

我们需要找到最大的数,就必须要将两个数进行比较,比较之后才知道谁大谁小。那么很简单,我们需要从这个list的第一个元素比较起,也就是比较5跟4的关系,发现5>4,所以5应该在4后面对吧?所以我们将5和4的位置进行一下互换。这时候这个list就变成[4, 5, 3, 2, 1]。接下来我们需要继续看5,这时候继续往下,5跟3进行比较,发现比3大于是跟3交换下位置。依次类推,当我们一轮比较完毕之后,我们把5放到了这个list的最后的位置上:[4, 3, 2, 1, 5]

接下来我们开始比较4了,同理进行比较后,把4放在了倒数第二的位置上:[3, 2, 1, 4, 5],有的同学会问,当4放到倒数第二个位置上的时候我们还需要拿它跟最后的5进行比较吗?答案是不用的。因为之前我们已经将5跟其他所有元素比较过了,确定它是最大的,所以已经沉底了,所以之后不用再跟5进行比较。这里同理4放在倒数第二个位置之后,以后的比较中已经没有4什么事儿了,只用管前面三个元素的比较即可。以此类推。最后我们把整个list比较完毕。


以上是我们手动的时候的办法。在编写编程代码的时候,其实也差不多是这个思路,但是每一步可能更加的中规中矩一些。接下来我们把每一步写下来,希望能加深大家的理解:

因为我们之前这个思路是每一轮都会确定一个数字的最后归属,那么五个数字需要多少轮呢?答案是四轮。因为将四个数字确定归属的位置之后,剩下那个数字肯定是在合适的位置了,所以只需要四轮即可,接下来我们就一轮轮的来写比较过程和变化过程吧。

第一轮(决定5的归属):

5大于4         [4, 5, 3, 2, 1]
5大于3         [4, 3, 5, 2, 1]
5大于2         [4, 3, 2, 5, 1]
5大于1         [4, 3, 2, 1, 5]

第一轮总共进行了4次比较。

第二轮(决定4的归属):

4大于3         [3, 4, 2, 1, 5]
4大于2         [3, 2, 4, 1, 5]
4大于1         [3, 2, 1, 4, 5]

第二轮总共进行了3次比较。

第三轮(决定3的归属):

3大于2         [2, 3, 1, 4, 5]
3大于1         [2, 1, 3, 4, 5]

第三轮总共进行了2次比较。

第四轮(决定2的归属):

2大于1         [1, 2, 3, 4, 5]

第四轮总共进行了1次比较。

至此,四轮比较全部完毕,我们可以注意到非常神奇的是,最后出来的这个list已经按照我们的想法,按从小到大排序好了。

在视频教程中我也进行了这个例子全程的板书,这是最后的成果截图,加深大家的理解:

零基础学python 15 经典算法:冒泡排序法


那么按照这个思路,python的代码要如何完成呢?

看我们的这个思路,其实是两层的嵌套比较完成的。第一层是我们的轮数,分别是一二三四轮,第二层是我们的轮内比较的次数,分别随着轮数的增加而减少。因此我们可以使用两个for循环来嵌套完成这个任务。

以下就是我们的冒泡排序法的代码:

def bubbleSort(nums):
    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
        for j in range(len(nums)-i-1):  # j为列表下标
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

外层循环变量为i,循环次数是list长度减一次,为什么呢?因为我们5个元素的list就需要比较4轮,所以减一。

接下来是j循环变量,它为列表元素的下标,可以看到后面我们需要取第j个和第j+1个元素来进行大小的比较。那么次数是如何计算的呢?我们知道range生成的数字序列如果只有一个参数的话是从0开始的,那么i最开始会取0,而我们的轮数是从第1轮开始的,那也就是i+1。而我们第一轮的时候进行了4次比较,而我们知道5-1=4,也就是list的长度减去轮数等于次数,而i+1正是我们的轮数,所以次数就是长度减去i+1即可。去掉括号也就是len(nums)-i-1

接下来的事情就变得简单了,比较两个相邻数字的大小,如果比后一个数字大的话,就进行互换位置。这里特别注意这个写法:nums[j], nums[j+1] = nums[j+1], nums[j]这样写其实是分别赋值的意思,会将nums[j+1]的值赋值给nums[j]而将nums[j]的值赋值给nums[j+1]。说白了就是这两个位置的数字进行了一次互换。在python中是可以这样写的,你也可以用于其他的代码中。而在其他一些语言之中可能不能这样写,必须定义一个临时变量用来存储它们的值才能够进行互换的。不过我们这里用在python中是完全没有问题的。

最后将排序好的list返回即可完成。


以上便是我们对于这个经典算法——冒泡排序法的详细教学。我希望通过我非常详尽的解答能够让大家清晰直观完整的了解到冒泡排序法从诞生到完成代码的全过程。因为它实在太经典了,从我的python课程中掌握它我想大家也能举一反三到其他的编程语言之中。后续的好处不言而喻。

 

以下是我们的视频教程:

在线观看:

 

 

高清源文件下载:

内容已经隐藏,请注册为本站会员后查看

 

 

感谢大家的收看,我们下期再见!

avatar

发表评论

您必须才能发表评论!