Python中的插入排序是什么？
插入排序是对数组进行排序的简单方法。在这种技术中，数组实际上分为已排序和未排序部分。未排序部分中的元素被拾取并放置在已排序部分中的正确位置。
数组元素从1到n遍历。
如果位置i处的数组元素大于其前任，则不需要移动它。
如果位置i处的数组元素小于其前驱，则需要将其向左移动，直到找到小于它的前驱或到达数组中的最左侧位置。
例子
借助一个例子，我们可以更清楚地理解上面的想法。假设我们有以下数组-
我们需要从索引1开始遍历数组（因为索引0没有前任）。
在索引1-
6大于其前身，因此无需执行任何操作。
在索引2-
1比它的前驱小，因此我们需要将它向左平移，除非我们找到比它小的前驱或者我们到达索引0。在这种情况下，我们将到达索引0。
在索引3-
在索引4-
向左移动2，直到找到小于2的前驱。
在索引5-
向左移动5，直到找到小于5的前驱。
因此，我们获得了已排序的数组。
插入排序是一种就地排序算法，时间复杂度为O(n^2)，空间复杂度为O(1)。
示例
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i] #获取每个元素
j = i-1
while j >= 0 and key &lit; arr[j] : #继续移动直到到达索引0或获得小于键的元素
arr[j + 1] = arr[j]
j=j-1
arr[j + 1] = key
arr = [4,6,1,7,2,5]
insertionSort(arr)
for i in range(len(arr)):
print (arr[i],end=" ")输出结果1 2 4 5 6 7