冒泡排序

基本思想

每次比较相邻的两个数,如果它们顺序错误就把它们交换过来

对7 9 2 5 3升序排列

  • 第一步:第一位的7和第二位的9比较,如果前面的值小于后面的,就交换--> 9 7 2 5 3
  • 第二步:同上,比较第二位的7和第三位的2,不用交换--> 9 7 2 5 3
  • 第三步:比较第三位的2和第四位的5,交换--> 9 7 5 2 3
  • 第四步:比较第四位的2和第五位的3,交换--> 9 7 5 3 2
    第一次循环结束,最小的数排在了最后面,在从前往后循环4次,就可以实现降序排列

python实现冒泡排序

#!/usr/bin/python
# encoding: utf-8

# 冒牌排序(降序)

# 待排序的列表
elem = [3, 10, 7, 4, 9, 8]

for i in range(1, len(elem) - 1):
    # 第i趟冒泡排序
    for j in range(0, len(elem) - i):
        # 比较相邻的两个数
        if elem[j] < elem[j+1]:
            elem[j],elem[j+1] = elem[j+1],elem[j]

print(elem) # [10, 9, 8, 7, 4, 3]

时间复杂度

从最关键的双层for循环可以看出,冒泡排序的时间复杂度为N的平方。

*参考资料《啊哈!算法》

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容