赞
踩
冒泡排序的基本思想:
1.对于一个待排序的序列,我们从第一个元素开始,让它依次与后面的元素进行比较,如果后面的元素比它大,就交换它们两个的位置,依次进行两两比较,这样一趟比较完就能选出一个最大的元素(默认是升序)至序列的末尾。
2.第二次我们从待排序序列的第二个元素开始,按照步骤1的方法,也让它依次与后面的元素进行比较,这样就能找到待排序序列中第二大的数。
3.重复上述步骤,直至序列中所有元素有序。
最常见的冒泡排序
- a1=[2,13,7,4,38,25,1,56,78,98,11]
- for i in range(0,len(a1)-1): #外层循环控制比较的趟数,i从0开始自增到len(a1)-1,len(a1)表示列表a1的长度
- for j in range(len(a1)-1-i): #内层循环因为有a[j+1],为了防止a[j+1]等于列表的长度,因此长度减1
- if a1[j]>a1[j+1]:
- a1[j],a1[j+1]=a1[j+1],a1[j] #若为逆序,则发生交换。
- print(a1)
相信上述的代码不难理解,但是小伙伴们有没有想过,要是用上述代码对这样的列表进行排序呢?
a2=[1,3,5,6,8,9,13,24,56,78],我们肉眼一眼就看出这已经是个有序的列表了,可是计算机和我们的编译器却不知道,它依然会傻乎乎的从第一个元素开始,依次从头到尾进行逐个比较,这样会大大降低程序的运行效率。
冒泡排序的改进一:不做无用功
- flag=True#设置一个标记变量
- for i in range (len(a2)-1):
- for j in range(len(a2)-1-i):
- if a2[j]>a2[j+1]:
- a2[j],a2[j+1]=a2[j+1],a2[j]
- flag=False#若发生元素的交换,则令flag=False
- if flag==True:#判断flag是否为True,若为True,说明未发生元素的交换。
- break#说明没有交换,序列已经有序,退出循环
- print(a2)
从上述代码可以看出,若待排序列表已经有序,则一趟比较就完成了排序,元素的比较次数和移动次数分别达到了9次和0次,即算法最好的时间复杂度为O(n)。
冒泡排序的改进二:双管齐下
不知道小伙伴们有没有见过这样的序列:a3=[78,65,96,105,48,34,12,10,7,4],当我们需要将序列中的元素按照从小到大进行排序发现序列中较大的数字多存在于列表的前边,而较小的数字又多存在于列表的尾部,如果此时我们还按照上述的排序算法,就会造成较小的数字向前移动的非常缓慢,可是这个问题,又怎么会难倒那些大神们呢?这就出现了双向冒泡排序,也称鸡尾酒排序。
由两个方向同时进行冒泡:首先从左到右扫描时,选出最大元素,然后从右向左扫描,选出最小元素,即交替的变换扫描方向,来回进行扫描,直到元素均有序,这就是双向冒泡排序。
- a3=[78,65,96,105,48,34,12,10,7,4]
- low=0
- high=len(a3)-1#列表长度减1是为了防止下面a[i+1]长度等于列表长度,而出现编译器报超出列表索引长度的错误
- while low<high:
- flag=False#设置一个标记变量
- #从前往后进行扫描,将最大的值放在列表的末尾
- for i in range(0,high):
- if a3[i]>a3[i+1]:#如果前面的值比后面的大,则交换
- a3[i],a3[i+1]=a3[i+1],a3[i]
- flag=True
- #从后往前进行扫描,将最小的值放在列表前面
- for i in range(high-1,low,-1):#range中第一个值是开始值,第二个值是结束值(不包括),第三个值是步长,-1代表逆序遍历
- if a3[i]<a3[i-1]:#如果后面的值比前面的小,则交换
- a3[i],a3[i-1]=a3[i-1],a3[i]
- flag = True
- if flag==False:#本趟没有发生交换,提前终止
- break
- low+=1
- high-=1
- print(a3)
其实很多时候与其它排序比较起来冒泡排序的效率并不算高,甚至有的情况下会变得很差,时间复杂度达到了O(n^2)。但是冒泡排序作为最经典的排序算法之一,简单易懂,而且是一种稳定的排序算法,对于初学排序的小伙伴们会很有帮助。此外,不管是去公司面试,还是考研尤其是专业课考数据结构这门课程的学校(有的学校喜欢考排序),都可能会考到冒泡排序或者让你给出优化改进的代码。本博主也是菜鸟一只,上述的理解只是个人拙见,欢迎各位小伙们指教,希望大家一起进步。
附:如果待排序序列中有两个元素是相等的,那么它们还是会进行比较,但是不会发生交换,这也就是我上面说冒泡排序是一种稳定的排序算法的原因了。有关排序算法的稳定性大家可以参考这个:https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7/9763250?fr=aladdin
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。