Python 算法教程（3）：插入排序详解
前言
插入排序类似于整理扑克牌，每次将新牌插入到已排序牌堆的正确位置。
一、算法原理
初始：[5, 2, 4, 6, 1, 3]
第 1 轮插入 2: [2, 5, 4, 6, 1, 3]
第 2 轮插入 4: [2, 4, 5, 6, 1, 3]
第 3 轮插入 6: [2, 4, 5, 6, 1, 3]
第 4 轮插入 1: [1, 2, 4, 5, 6, 3]
第 5 轮插入 3: [1, 2, 3, 4, 5, 6]二、代码实现
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr三、复杂度
最好 O(n)，平均 O(n²)，最坏 O(n²)，空间 O(1)，稳定
四、应用
小规模数据、几乎有序数据
总结
插入排序是三种简单排序中最实用的。
下一篇：希尔排序
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
