Python——关于排序算法（插入法）

接上一篇冒泡排序法，今天来讲一下插入排序法（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要稍微快一些，感兴趣的童鞋可以自己试验一下哦。