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+ 瀏覽

開啟你的 職業生涯

透過完成課程來獲得認證

開始入門