插入排序算法从字面上的理解就是把数据插入到一个已经排好序的队列中。朴素一点理解,就是在那里已经站了一排人,从矮到高排的,现在有一个人要按高矮排这个队列里。那应该插入到哪个位置呢,不知道啊,那就从最高的位置开始比较,一个个往前比较,然后插入到合适的位置。
算法的关键点:
插入排序算法是稳定性的排序算法,时间复杂度是o(n^2)。
看一个简单的例子:
5, 3, 2, 1 一趟插入排序是如何进行
插入排序算法,第一个数认为是已经排好序的,从第二数 3 开始。
开始比较时, tmp = 3, i = 1 记录当前的值与下标
第一次比较: 5, 3, 2, 1;3比5小, 把5移动到3的位置。
此时5留出了一个空位置 j = 0,而前面没有数据了。
把3插入到j = 0 位置的,就会得到第一趟插入排序的算法的结果: 3,5,2,1。
第二趟排序从下一个位置开始,重复上一次的过程,一直到数组的最后。
下面我们看一下算法的代码实现:
def insert_sort(elements):
n = len(elements)
for i in range(1, n):
tmp = elements[i]
k = i
for j in range(i, 0, -1):
if tmp < elements[j - 1]:
elements[j] = elements[j - 1]
k = j - 1
else:
break
elements[k] = tmp
if __name__ == '__main__':
arr = [5, 2, 3, 1]
insert_sort(arr)
print(arr)
运行后输出结果:
[1, 2, 3, 5]
更多内容可以关注公众号: IT技术漫漫谈
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。