什么是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)。

更多Python相关文章，请阅读：Python 教程

例子

definsertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i] #获取每个元素
        j = i-1
        while j >= 0 and key < arr[j] : #不断向左移动直到到达索引0或者找到比key小的元素
                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