python学习笔记_第30天(插入排序+快速排序)

1544-陈同学

发表文章数:60

热门标签

,
首页 » 数据结构 » 正文

插入排序

插入排序(Insertion Sort)的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

插入排序分析

python学习笔记_第30天(插入排序+快速排序)

def insertion_sort(alist):
    '''插入排序'''
    n = len(alist)
    for j in range(1, n):  # 第一个数默认有序,从第二个数开始操作
        i = j  # 内层循环的起始索引
        while i > 0:
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
                i -= 1

测试

if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    insertion_sort(li)
    print(li)

执行结果:
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 最优时间复杂度:O(n) (有序列表内层循环可直接break跳出,负责度变成O(1))
  • 最坏时间复杂度:O(n^2)
  • 稳定性:稳定

插入排序代码优化

def insertion_sort(alist):
    '''插入排序'''
    n = len(alist)
    for j in range(1, n):
        i = j
        while i > 0:
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
                i -= 1
            else:  # 有序部分值有一个大于比较值时,则不用后续比较
                break  # 跳出当前循环

选择排序与插入排序的区别

  • 选择排序:右侧无序数据中选择最大(小)值放到左侧已排序数据的后面
  • 插入排序:取右侧无序数据的第一个数与左侧有序数据比较,在合适位置按序插入

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本
希尔排序是把元素按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序过程

希尔排序的基本思想是:将数组列在一个表中并对列分别进行插入排序,重复这过程,不过每次用更长的列(步长更长了,列数更少了)来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身还是使用数组进行排序
例如组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果以步长为5开始进行排序。如下拆分,竖着的列是按照此步长拆分的组:

13|14|94|33|82
25|59|94|65|23
45|27|73|25|39
10|

然后对每列进行排序(在一次内部循环中完成):

10|14|73|25|23
13|27|94|33|39
25|59|94|65|82
45|

按分组排序后,用原先分组的步长重新组合回一个列表,得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。然后缩短步长,假设以3为步长再次进行拆分排序:

10|14|73
25|23|13
27|94|33
39|25|59
94|65|82
45|

排序后重组变为:[10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94]

10|14|13
25|23|33
27|25|59
39|65|73
45|94|82
94

缩小步长直至步长为1,再次进行普通插入排序确认(此时就是简单的插入排序了)

希尔排序的分析

python学习笔记_第30天(插入排序+快速排序)

def shell_sort(alist):
    '''希尔排序 -- 插入排序的一种更高效的改进版本'''
    n = len(alist)
    gap = n // 2
    while gap >= 1:  # list的步长为1时,可视为普通插入排序,再次确认排序的正确性
        for j in range(gap, n):  # 希尔算法与普通插入算法的区别在于gap步长
            i = j  # i=[gap,gap+1,...n-1]
            while i > 0:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap  # 通过步长将整个list分解成多个部分进行排序与重组
                else:  # 优化函数,避免与已排序部分的无意义比较
                    break
        gap //= 2  # 缩短gap的步长

测试

if __name__ == '__main__':
    li = [49, 58, 65, 97, 26, 13, 27, 49, 55, 4]
    print(li)
    shell_sort(li)
    print(li)

执行结果:
[49, 58, 65, 97, 26, 13, 27, 49, 55, 4]
[4, 13, 26, 27, 49, 49, 55, 58, 65, 97]

时间复杂度

  • 最优时间复杂度:乱序数列也可以通过调整步长提升时间复杂度,统计约为O(n^1.3)
  • 最坏时间复杂度:O(n^2)(带入gap=1时的特殊情况所得)
  • 稳定想:不稳定

未经允许不得转载:作者:1544-陈同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《python学习笔记_第30天(插入排序+快速排序)》 发布于2021-02-20

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录