Python 程序中的插入排序

在本文中，我们将了解在 Python 3.x 及更早版本中实现插入排序的情况。

算法

• 在每次迭代中通过扩展排序数组，对输入元素进行迭代。

• 将当前元素与排序数组中可用的最大值进行比较。

• 如果当前元素较大，则将其留在原位并继续进行下一个元素，否则找到其在排序数组中的正确位置，并将它移动到数组中的该位置。

• 可以通过将排序数组中大于当前元素的所有元素向右移动一个位置来实现这一点。

现在我们来看一下该算法的可视化表示

现在我们来看一下实现

示例

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # Move elements of arr[0..i-1], that are greater
      than key,
      # to one position ahead of their current position
      j = i-1
      while j >=0 and key < arr[j] :
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# main
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

输出

The sorted array is:
a
i
l
o
r
t
t
u

时间复杂度： O(n*2)

辅助空间： O(1)

所有变量均在全局框架中声明，如下所示−

结论

在本文中，我们了解到了插入排序及其在 Python 3.x 或更早版本中的实现。

Pavitra

更新于: 2019 年 9 月 26 日

1K+ 浏览

开启你的 职业生涯

通过完成课程来获得认证

开始入门