冒泡排序(Python实现)
程序员文章站
2022-03-24 15:44:56
...
冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,一次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
算法原理
冒泡排序算法的原理如下:
-
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
-
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
-
针对所有的元素重复以上的步骤,除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
def bubble_sort(alist):
for j in range(len(alist)-1):
for i in range(len(alist)-1-j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
return alist
if __name__ == '__main__':
li = [1,3,4,2,9,5,8]
print(li)
bubble_sort(li)
print(li)
思路:若列表有存在n个元素
第1次开始比较的时候经过n-1次的比较将最大的数传到最后
第2次开始比较的时候经过n-2次的比较将第二大的数传到倒数第二个
.......
第N次需要交换(n-N)次
一共需要交换(n-1)次
也可以换成下面这种写法
def bubble_sort(alist):
for j in range(len(alist)-1,0,-1):
for i in range(j):
if alist[i] > alist[i + 1]:
alist[i], alist[i + 1] = alist[i + 1], alist[i]
return alist
if __name__ == '__main__':
li = [1,3,4,2,9,5,8]
print(li)
bubble_sort(li)
print(li)
这样的时间复杂度是O(n**2)
但是如果本来的列表顺序就是顺序排列呢?每次仍然需要排列N**2次有点浪费
def bubble_sort(alist):
for j in range(len(alist)-1):
count = 0
for i in range(len(alist)-1-j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
count += 1
if count == 0:
return alist
return alist
if __name__ == '__main__':
li = [1,3,4,2,9,5,8]
print(li)
bubble_sort(li)
print(li)
我们可以设置一个变量,如果走完一轮还没有发现有任何交换过的次数,
说明此时列表是顺序的(最优情况下时间复杂度是O(n))
直接返回即可
上一篇: 排序算法之基数排序(桶排序)
下一篇: 冒泡排序(python实现)