云社区 博客 博客详情
云社区 博客 博客详情

使用python实现冒泡、选择、插入基础排序

misssuk 发表于 2019-12-23 20:24:15 12-23 20:24
misssuk 发表于 2019-12-23 20:24:15 2019-12-23
0
0

【摘要】 冒泡排序依次比较相邻两元素,若前一元素大于后一元素则交换之,直至最后一个元素即为最大;然后重新从首元素开始重复同样的操作,直至倒数第二个元素即为次大元素;依次类推。如同水中的气泡,依次将最大或最小元素气泡浮出水面。实现#冒泡排序defbubble_sort(li):#建立一个标识符flag=Falseforiinrange(len(li)-1):forjinrange(len(...

冒泡排序

依次比较相邻两元素,若前一元素大于后一元素则交换之,直至最后一个元素即为最大;

然后重新从首元素开始重复同样的操作,直至倒数第二个元素即为次大元素;

依次类推。如同水中的气泡,依次将最大或最小元素气泡浮出水面。

实现

# 冒泡排序
def bubble_sort(li):
    # 建立一个标识符
    flag = False
    for i in range(len(li)-1):
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                flag = True
        # 如果没进行交换,则本身有序,直接break
        if not flag:
            break
    return li

算法分析

  • 平均时间复杂度:O(n2),标准的内外两层循环
  • 最好时间复杂度:O(n),如果有序,那么第一趟就ok了
  • 最坏时间复杂度:O(n2)
  • 空间复杂度:O(1)
  • 稳定性:稳定的

选择排序

首先初始化最小元素索引值为首元素,依次遍历待排序数列,若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置,直至遇到尾元素,结束一次遍历,并将最小索引处元素与首元素交换;

然后,初始化最小索引值为第二个待排序数列元素位置,同样的操作,可得到数列第二个元素即为次小元素;以此类推。

实现

# 选择排序 O(n^2)
# 从第一个元素开始选择最小的元素放在第一位,然后再选择第二个元素
def select_sort(li):
    for i in range(len(li)-1):
        # 第i趟 无序区范围i到最后
        min_pos = i # 无序区最小值位置
        for j in range(i+1, len(li)):
            if li[j] < li[min_pos]:
                min_pos = j
        li[i], li[min_pos] = li[min_pos], li[i]

算法分析

  • 平均时间复杂度:O(n2),嵌套双循环
  • 最好时间复杂度:O(n2),每次要找最大最小肯定是要遍历一遍的
  • 最坏时间复杂度:O(n2)
  • 空间复杂度:O(1)
  • 稳定性:稳定的

插入排序

 

将列表分为有序区和无序区两个部分,最初有序区只有一个元素,即第一个元素。

然后每次从无序区选择一个元素,插入到有序区中,直到无序区为空。

如下图,橙色为有序区,浅蓝色为无序区。

实现

# 选择排序 O(n2)
def insert_sort(li):
    # i表示从下标1开始的数字, 第二个元素
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        # 只要往后挪就循环
        while j >= 0 and li[j] > tmp:
            # 如果j = -1停止挪, 如果li[j]小于tmp停止挪
            li[j + 1] = li[j]
            j -= 1
        # j位置在循环结束的时候要么是-1要么是比tmp小的值
        li[j+1] = tmp

算法分析

  • 平均时间复杂度:O(n2)
  • 最好时间复杂度:O(n),如果有序,那么每个元素都已经在在它的待排子序列的合适位置,不用找合适位置
  • 最坏时间复杂度:O(n2)
  • 空间复杂度:O(1)
  • 稳定性:稳定的

~>.<~

文章来源: www.cnblogs.com,作者:Nolinked,版权归原作者所有,如需转载,请联系作者。

原文链接:https://www.cnblogs.com/pungchur/p/12080326.html

登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 0
点赞
分享文章到微博
分享文章到朋友圈

评论 (0)


0/1000
评论

登录后可评论,请 登录注册

评论

您没有权限执行当前操作

温馨提示

您确认删除评论吗?

确定
取消
温馨提示

您确认删除评论吗?

删除操作无法恢复,请谨慎操作。

确定
取消
温馨提示

您确认删除博客吗?

确定
取消

确认删除

您确认删除博客吗?

确认删除

您确认删除评论吗?

温馨提示

登录超时或用户已下线,请重新登录!!!

确定
取消