Python——关于排序算法(插入法)

这是奔跑的键盘侠的第97篇文章

接上一篇冒泡排序法,今天来讲一下插入排序法(insertion sorting),接下来几期还会有选择排序法、合并排序法、快速排序法等等,敬请期待哦。

插入排序法(Insertion Sorting)

先来看一下百度百科的定义:

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。 百度百科

插入排序算法的原理:

比如要排序n个数字,同样,也是进行n轮循环比较并操作。每一轮,都是将未排序过首个数字,与前方已排序好的队列中的元素,依次进行比较,将该数字不断(往前或者往后)置换,直到该数字排好序。

举个例子:

有列表[3,8,2,1,7,6,5]

用插入法操作:

第一轮:

3是已排序好的,将未排序的首个数字8与3进行比较,8大则8不动

3,8

第二轮:

3,8是已排序好的,将未排序的首个数字2与8进行比较,2小则8,2互换:

3,2,8,再继续把2与3比较,2小则3,2互换:

2,3,8

第三轮:

2,3,8是已排序好的,将未排序的首个数字1与8进行比较,1小则8,1互换:

2,3,1,8,再继续把1与3比较,1小则3,1互换:

2,1,3,8,再继续把1与2比较,1小则2,1互换:

1,2,3,8

第四轮:

1,2,3,8是已排序好的,将未排序的首个数字7与8进行比较,7小则8,7互换:

1,2,3,7,8,再继续把7与3比较,7大则7不动(本轮结束)

第五轮:

1,2,3,7,8是已排序好的,将未排序的首个数字6与8进行比较,6小则8,6互换:

1,2,3,7,6,8

…………

1,2,3,6,7,8,再继续把6与3比较,6大则6不动(本轮结束)

第六轮:

1,2,3,6,7,8是已排序好的,将未排序的首个数字5与8进行比较,5小则8,5互换:

1,2,3,6,7,5,8

…………

1,2,3,6,5,7,8

1,2,3,5,6,7,8,再继续把5与3比较,5大则5不动(本轮结束)

本轮结束

直到后方无未排序的数字,排序结束。

插入排序法总的平均时间复杂度为

。假设列表中的元素是刚好逆序的:比如[6,5,4,3,2,1]那第一轮就要交换1次,第二轮2次……5次,总共次数就是1/2*5*(5+1)也就是1/2*(N-1)*N,时间复杂度是n的平方。

coding

#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time    : 2019-03-25 20:23
# @Author  : Ed Frey
# @File    : Insertion_sorting.py
# @Software: PyCharm
from time import clock

def timer(f):
    def _f(*args):
        t0 = clock()
        f(*args)
        return clock() - t0
    return _f

def insertion_sorting(num:list):
    lenth = len(num)

    for i in range(1,lenth):
        while i>0 and num[i-1]>num[i]:
            num[i-1],num[i] = num[i],num[i-1]
            i -= 1
        print(num)
    return num


if __name__ == '__main__':

    num = [3,8,2,1,7,6,5]
    time = timer(insertion_sorting)(num)
    print(time)

运行结果如下:

[3, 8, 2, 1, 7, 6, 5]

[2, 3, 8, 1, 7, 6, 5]

[1, 2, 3, 8, 7, 6, 5]

[1, 2, 3, 7, 8, 6, 5]

[1, 2, 3, 6, 7, 8, 5]

[1, 2, 3, 5, 6, 7, 8]

6.0000000000004494e-05

bubble sort 和insertion sorting比较

上一期的bubble sort 有2个版本,改进前的版本耗时略多,改进后的版本耗时减少很多,经过我自己简单测试,insertion sorting是比改进前的bubble sort更高效,原因很简单,改进前的bubble sort 要进行n轮循环,而且每轮循环都要进行逐个比较;而insertion sorting是插入前方已排序好的队列中,循环过程中,只要数字移动至相应位置,本轮循环就提前结束了。

改进后的bubble sort比insertion sorting要稍微快一些,感兴趣的童鞋可以自己试验一下哦。

本文分享自微信公众号 - 奔跑的键盘侠(runningkeyboardhero)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏嵌入式程序猿

Flash如何模拟EEPROM

很多的MCU控制器不带有片上EEPROM,但是我们有时候鉴于成本的考虑又不想外扩EEPROM,所以经常用Flash来模拟EEPROM存储,但是Flash都是块擦...

30050
来自专栏秃头哥编程

数据库之索引总结

索引在数据库中可以说是相当重要的一块知识点了,也是面试经常被问的,这篇文章就总结一下索引相关的知识点,包括索引的底层实现原理,索引的分类,最左匹配原则等。

9130
来自专栏我是攻城师

如何通过Java反射获取泛型类型信息

关于Java泛型,很多人都有一个误解,认为Java代码在编译时会擦除泛型的类型,从而在运行时导致没法访问其类型,这其实并不完全正确,因为有一部分泛型信息是可以在...

2.2K20
来自专栏小小挖掘机

面试常考-链表反转解析

你是否有过这种体会:看别人的代码,当时看得很明白了,但是,过段时间,自己却怎么都写不出来?这是怎么回事,可能我们也清楚。别人的思维你是无法拷贝的,形成之前不具备...

11130
来自专栏秃头哥编程

Redis内存回收策略

Redis会因为内存不足而产生错误,也会因为回收过久而导致系统长期的停顿,因此了解掌握Redis的回收策略十分重要。当Redis的内存达到规定的最大值时,可以进...

33620
来自专栏秃头哥编程

Java开发神器Lombok的安装与使用

项目中经常使用bean,entity等类,绝大部分数据类类中都需要get、set、toString、equals和hashCode方法,虽然eclipse和id...

10930
来自专栏数值分析与有限元编程

Fortran如何实现矩阵与向量的乘法运算

矩阵是二维数组,而向量是一维数组,内置函数matmul不能实现矩阵与向量的乘法运算。在这一点Fortran不如matlab灵活。

61020
来自专栏秃头哥编程

程序员编程十大原则,学不会就是真小白

大多数情况下,文档不用于通信,它用于记录。大多数要求仍然通过口头交流传达,但文件没有记录,后续工作很容易!

10820
来自专栏Crossin的编程教室

len(x) 击败 x.len(),从内置函数看 Python 的设计思想

它们预先定义在内置命名空间中,开箱即用,所见即所得。Python 被公认是一种新手友好型的语言,这种说法能够成立,内置函数在其中起到了极关键的作用。

9620
来自专栏秃头哥编程

Redis常用技术-----使用Lua语言

Redis命令的计算能力并不算很强大,使用Lua语言则可以在很大程度上弥补Redis的这个不足。在Redis中,执行Lua语言是原子性,也就是说Redis执行L...

13020

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励