发布于2019-10-11 14:44 阅读(1340) 评论(0) 点赞(7) 收藏(4)
冒泡排序(Bubble Sort),是经典的排序算法,基本上我们学习任何语言都会接触到冒泡排序。
它的算法思想是,重复地遍历要排序的列表,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历列表的工作是重复地进行直到没有再需要交换,也就是说该列表已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
比如我们有下面这样一个列表:
li = [10,8,4,7,5]
每次遍历列表每个元素,然后比较前后两个元素的大小,如果前面的数大于后面的数,就交换位置,否则什么都不做。
下面是第一次遍历后的效果,我们将列表竖起来,可以看到最大值(10)像一条小鱼吐的一个泡泡逐渐冒到了水面:
这样我们可以确定一个程序上的循环:
for j in range(len(li)-1): # 列表中一个5个数,比较为两两比较,因此实际次数为4次
if li[j] > li[j + 1]: # 判断前面的数是否大于后面的数
li[j], li[j + 1] = li[j + 1], li[j] #大于则交换位置
语句解释:
len(li) - 1:len(li) 获取列表li中的元素个数;这里我们只进行一次循环的情况,循环的次数为元素的个数 -1;
li[j] > li[j + 1]:就是比较大小啦;
li[j], li[j + 1] = li[j + 1], li[j]:Python 中的多元赋值,也是一种很方便的交换变量值的方式,省去了中间变量。
li[j], li[j + 1] = li[j + 1], li[j]
等价于
temp = li[j]
li[j] = li[j+1]
li[j+1]=temp
第一轮比较已经确定最大值 10,因此后面的比较 10 不需要参与;
第二轮比较就是 len(li) -1-1,本来比较就是 len(li) -1,已经有一个值不用参与了,则需要再减去 1,第二轮确定次大值 8;
第三轮时 10,8 已经确定,因此比较的次数就变成了 len(li) -1-2;
以此类推,比较的次数实际是在以递减的方式减少;
因此可以确定内层循环的最终写法:
for j in range(len(li)-1-i): # i为一个递增的数,减去递增,就是递减嘛
每一轮循环就是将一个尚未排序的最大值进行了一次冒泡。
内层循环已确定,外层循环就简单了。
每次冒泡确定一个最大值,那么 n 个数比较,只需要进行 n-1 次冒泡就行了。
for i in range(len(li)-1): # n-1次冒泡
li = [10,8,4,7,5]
for i in range(len(li)-1):
for j in range(len(li)-1-i):
if li[j] > li[j + 1]:
li[j], li[j + 1] = li[j + 1], li[j]
print(li)
作者:加班是一种习惯
链接:https://www.pythonheidong.com/blog/article/134306/00a168114612521bf57f/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!