插入算法
思想
- 和选择排序类似的思想:将数据分成两个部分,排好序和待排序的部分。
- 不同之处在于
- 选择:从未排序的部分选择最小数据放到前面排好序的数据中
- 插入:将未排序的部分第一个数据和前面的数据比较,插入相应的位置
https://www.cnblogs.com/onepixel/articles/7674659.html
栗子
将1看做是排好序的数据,后面是待排序的数据
[1,] [8, 9, 7, 3, 5, 2, 6, 4]
- 第一步:待排序的数据第一个是8,比1大,放到1的后面
[1, 8,] [9, 7, 3, 5, 2, 6, 4] - 第二步:待排序的第一个数据是9,比前面排好序的1和8都要大,所以排在8的后面
[1, 8, 9,] [7, 3, 5, 2, 6, 4] - 第三步:待排序的第一个数据是7,放到1的后面
[1, 7, 8, 9,] [3, 5, 2, 6, 4] 以此类推......
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
时间复杂度
- 最优时间复杂度:
- 最坏时间复杂度:
- 稳定性:稳定
代码实现
def insert_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
return alist
def insert_sort1(alist):
n = len(alist)
for i in range(n):
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]
return alist