Python中的插入排序是什么？

• Z时代
• 2024-01-10
• 分类：综合

插入排序是对数组进行排序的简单方法。在这种技术中，数组实际上分为已排序和未排序部分。未排序部分中的元素被拾取并放置在已排序部分中的正确位置。

• 数组元素从 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

以上是 Python中的插入排序是什么？ 的全部内容， 来源链接： utcz.com/z/351662.html