排序算法（3）：插入排序
问题
排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]
插入排序
插入排序将序列分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的适当位置。重复此过程直到所有元素排序完成。
图解
- 初始化第一个元素为已排序部分，从未排序部分取第一个元素，插入到已排序部分的适当位置，主要是通过将大于待排序元素的位置后移
- 重复上述过程直到所有元素完成排序
代码
def insertion_sort(nums):
n = len(nums)
for i in range(1, n):
key = nums[i]
j = i - 1
while j >= 0 and key < nums[j]:
nums[j + 1] = nums[j]# 将大于目标值的元素后移
j -= 1
nums[j + 1] = key
return nums
时间复杂度
插入排序的时间复杂度为 O(n2)
原文地址：https://blog.csdn.net/m0_45284589/article/details/144372859
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！