冒泡排序&优化:Python实现(低级排序法)
维基百科:
冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,时间复杂度O(n²)。
说白了,步骤是这样子的:
- 列表每相邻的两个数若果前面的数比后面的数大(小),则交换两个数
- 一趟排序完成后,则无序区减少一个数,有序区增加一个数
-
核心是:大数下沉,小数上冒。每一次总能找到一个最大的或者最小的
不啰嗦了,上代码
def bubble_sort(li):
for i in range(len(li)-1):#外循环表示排序的趟数4
for j in range (0,len(li)-1-i):#内循环表示每趟比较的次数
if li[j] > li[j+1]:#由小到大排序
li[j],li[j+1] = li[j+1],li[j]#这里需要注意的两轮循环的次数。在第一轮循环的时候,次数为数组长度减1。第二轮循环的次数为剩余需要排序数量。这个是这个算法的精华
return li
def scan(a = ",", b = "请输入一组值",c = "w"):#收集用户需要排序的数据
d = input(b + ":")
f = d.split(a)
g = []
for q in f:
if c == "w": #当输入c="w"时,转化为整数数值赋给列表
g.append(int(q))
elif c == "e": #当c="e"时,转化为浮点数付给列表
g.append(float(q))
elif c == "r": #当c="e"时,把字符串值赋给列表
g.append(q)
return g
li = scan()
li = bubble_sort(li)
print(li)
冒泡排序代码优化
如果列表中有一段是有序的,上面的代码依然会乐此不疲的一趟一趟的比较,这大大减小了效率,根据这个思想我们对代码进行优化:
若本次冒泡排序过程中没有任何交换,说明序列已经有序,停止交换,说白了,就是如果一趟中没有任何交换就说明这一趟中所有的数据是一个有序的,剩下的数据不需要再进行排序了
代码如下
def bubble_sort(li):
for i in range(len(li)-1):#外循环表示排序的趟数4
exchange = False#设置一个是否进行交换的量,先假设设没有发生交换
for j in range (len(li)-1-i):#内循环表示每趟比较的次数
if li[j] > li[j+1]:#由小到大排序
li[j],li[j+1] = li[j+1],li[j]
exchange = True#发生了交换
if not exchange:# 在一趟过程中没有发生交换,就认为已经排好序了,不需要交换,退出循环
break
li = []
while 1:#收集用户需要排序的数据
a = input('请输入您要查询的数字,回车输入选一个数据,#结束:')
if a=='#':
break
a = int(a)
li.append(a)
print(f'您要排序的列表是{li}')
bubble_sort(li)
print(f'冒泡排序完成后的列表是{li}')