数据结构与算法(冒泡排序)
程序员文章站
2022-07-08 14:52:26
...
冒泡排序
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把它们交换过来。遍历数列的工作是重复的进行直到没有在需要的交换,也就是说该数列已经排序完成,这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡算法的运作如下:
- 比较相邻的元素,如果第一个元素大于第二个元素(升序),就交换它们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这步完成后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个
- 持续每次越来越少的元素重复上面的步骤,直到没有任何一堆数字需要比较。
冒泡算法分析
交换过程图示(第一次):
那么我们需要进行n-1次冒泡过程,每次对应的比较次数如下图所示:
Pass | Comparisons |
---|---|
1 | n-1 |
2 | n-2 |
3 | n-3 |
… | … |
n-1 | 1 |
代码实现
def bubble_sort(alist):
"""冒泡排序"""
for j in range(len(alist)-1):
for i in range(len(alist)-j-1):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
return alist
时间复杂度
- 最优时间复杂度:O(n)表示遍历一次发现没有任何可交换的元素,排序结束
- 最坏时间复杂度:
- 稳定性:稳定
冒泡复杂度的优化
对于一开始就有序的序列,时间复杂度为O(n)
#优化冒泡算法
def bubble_sort(alist):
"""冒泡排序"""
for j in range(len(alist)-1):
count = 0
for i in range(len(alist)-j-1):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1
if 0 == count:
return alist
上一篇: 数据结构与算法_冒泡排序
下一篇: Blogger导入XML文件出错分析