和前面介绍的冒泡排序算法选择排序算法类似,插入排序算法也是一种基础排序算法,其时间复杂度也是O(n^2)。实现思路是:从当前位置开始,从后往前遍历其之前的序列,如果比当前位置的值大,则往后挪动一位,直到遇见比其小的位置结束

举个例子

用插入算法对 [33, 14, 27, 10, 35] 实现升序排序过程如下:

1) 14和 [33] 比较,33比14大,所以33往后挪动一位;

[14, 33, 27, 10, 35]

2) 27和 [14, 33] 比较,33比27大,所以33往后挪动一位,但14比27小,这一轮结束;

[14, 27, 33, 10, 35]

3) 10和 [14, 27, 33] 比较,33、27、14都比10大,全部往后挪动一位;

[10, 14, 27, 33, 35]

4) 35和 [10, 14, 27, 33] 比较,33比35小,本轮结束。

[10, 14, 27, 33, 35]

代码示例

def insert_sort(lst):
    for i in range(1, len(lst)):
        pos = i - 1
        temp = lst[i]
        while pos >= 0 and lst[pos] > temp:
            lst[pos + 1] = lst[pos]
            pos -= 1
        lst[pos + 1] = temp

lst = [33, 14, 27, 10, 35]
insert_sort(lst)
print(lst)

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/210