手机版
你好,游客 登录 注册 搜索
背景:
阅读新闻

Python数据结构之冒泡排序和选择排序

[日期:2018-08-19] 来源:Linux社区  作者:kk328 [字体: ]

Python数据结构之冒泡排序

冒泡排序是一种基础排序算法,在python中,我们利用列表的的方式来完成,它对列表中的元素进行重复的遍历,在遍历的同时进行比较,如果两个数没有按照我们规定的顺序进行排列,就按照我们预先设定好的是顺序或者逆序输出,类似于烧开水时的气泡,主要操作如下:

  • 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

时间复杂度

  • 最优时间复杂度:O(n) (表示遍历一次发现没有任何可以交换的元素,排序结束。)
  • 最坏时间复杂度:O(n2)
  • 稳定性:稳定

附上完整代码:

def bubble_sort(list):
    for j in range(len(list)-1,0,-1):
        for i in range (j):
            if list[i]>list[i+1]:
                list[i],list[i+1]=list[i+1],list[i]
List=[1,3,2,8,4,6,9,7]
bubble_sort(List)
print(List)

Python数据结构之选择排序

选择排序(select_sort)是一个基础排序,它主要通过查找已给序列中的元素的最大或者最小元素,然后将其放在序列的起始位置或者结束位置,并通过多次这样的循环完成对已知序列的排序,在我们对n个元素进行操作时,我们至少需要n-1次。

def select_sort(list):
    n=len(list)
    #进行n-1次操作
    for i in range(n-1):
        min_dex=i
        #记录最小的位置
        for j in range(i+1,n):
            #从i+1选取最小位置
            if list[j]<list[min_dex]:
                min_dex=j
        #最小位置不对应进行交换
        if min_dex !=i:
            list[i],list[min_dex]=list[min_dex],list[i]
List=[0,3,1,2,9,4,6,5,8,7]
select_sort(List)
print(List)

Linux公社的RSS地址:https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址https://www.linuxidc.com/Linux/2018-08/153592.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款