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] #get each element
      j = i-1
      while j >= 0 and key &lit; arr[j] : #keep shifting until reaching index 0 or getting an element smaller than 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

pawandeep

更新于: 2021-06-11

5K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习