天津建筑工程信息平台_刚刚合肥最新通告_好用的seo软件_杭州seo博客有哪些

问题

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

插入排序

插入排序将序列分为已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的适当位置。重复此过程直到所有元素排序完成。

图解

1. 初始化第一个元素为已排序部分，从未排序部分取第一个元素，插入到已排序部分的适当位置，主要是通过将大于待排序元素的位置后移
   
2. 重复上述过程直到所有元素完成排序

代码

def insertion_sort(nums):n = len(nums)for i in range(1, n):key = nums[i]j = i - 1while j >= 0 and key < nums[j]:nums[j + 1] = nums[j]	# 将大于目标值的元素后移j -= 1nums[j + 1] = keyreturn nums

时间复杂度

插入排序的时间复杂度为 O(n²)