思路
每次将一个数字插入到一个有序数组中，成为一个更长的有序数组，在有限次操作之后，数组整体有序
动图演示
根据上方演示，可以直观的看出，从后面依次取数字，然后插入到前方有序的数组中
图片来源： https://visualgo.net/zh/sorting
边想边写
- 既然需要从后续数组中依次取值，所以必然会遍历这个数组
def insert_sort(nums):
length = len(nums)
for i in range(1, length):
# ...
- 当取出一个数字时，我们需要与前面的有序数组依次比较，找到「合适的插入位置」，根据演示图，是逆序遍历「有序数组」的
def insert_sort(nums):
length = len(nums)
for i in range(1, length):
for j in range(i-1, -1, -1):
# ...
这里解释下 range(i-1, -1, -1)的写法，这是python的逆序遍历
第一个参数
i-1， 这个很好理解，我在第i个位置，取出这个数字，自然需要逆序遍历，i之前的有序数组，所以是从i-1第二个参数
-1，这个是遍历的步长，这里表示每次遍历的跨度为1，因为是逆序，遍历的索引需要不断减小，所以是-1第三个参数
-1，表示「逆序遍历」
- 在逆序遍历有序数组的过程中，不断比较，找到合适位置并“插入”
def insert_sort(nums):
length = len(nums)
for i in range(1, length):
for j in range(i-1, -1, -1):
if nums[i] >= nums[j]:
break
elif nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i]
在大于等于的情况下，此时我们所取出来的
nums[i]是前面「有序数组」中的最大值，所以可以提前终止此内循环，避免后续无用的操作在小于的情况下，则需要将
nums[i]与有序数组部分逆序比较，这里的 “插入” 并非是真的插入，而完成 “插入”操作，我们可以使用「值交换」完成一次「值交换」后，还需要向前比较，所以应该更改它们的索引值，
i是我们取出来的数字的索引，当交换发生后，此时i所表示的值发生了改变，此时我们应该将i重新表示为 「取出来的数字」，看文字有点绕，看下图
j移动是交给循环的，所以我们只需要让i向前移动即可
完整代码
def insert_sort(nums):
length = len(nums)
for i in range(1, length):
for j in range(i-1, -1, -1):
if nums[i] >= nums[j]:
break
elif nums[i] < nums[j]:
nums[i], nums[j] = nums[j], nums[i]
i = j # 或者 i -= 1
return nums
用例测试
测试用例： https://leetcode-cn.com/submissions/detail/89203696/testcase/
使用此算法，用时：156.1655251979828
复杂度分析
- 时间复杂度：O(n2)，这里 N 是数组的长度；
- 空间复杂度：O(1)，使用到常数个临时变量。
插入排序的特点（重要）
- 「插入排序」可以提前终止内层循环；
- 在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 O(1)，因此「插入排序」可以作为高级排序算法的一个子过程（后面再「归并排序」和「快速排序」算法里我们会看到）。
总结
- 优化：「将一个数字插入一个有序的数组」这一步，可以不使用逐步交换，使用先赋值给「临时变量」，然后「适当的元素」后移，空出一个位置，最后把「临时变量」赋值给这个空位的策略（就是上面那张图的意思）。
- 由于「插入排序」在「几乎有序」的数组上表现良好，特别地，在「短数组」上的表现也很好。因为「短数组」的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用「插入排序」。