如何使用Python實現(xiàn)插入排序和選擇排序

這篇文章主要介紹如何使用Python實現(xiàn)插入排序和選擇排序，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

插入排序

如下圖所示，插入排序的實現(xiàn)思路顧名思義，就是 不斷地在一個已經(jīng)是有序的數(shù)組中，尋找合適位置并插入新元素 。

具體實現(xiàn)步驟為：

首先我們把整個數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個元素，就是數(shù)組的第一個元素。

接在有序區(qū)間之后的一個元素就是準備插入的元素，在圖中就是標為綠色的元素，在有序區(qū)間內(nèi)尋找位置并插入。

其尋找邏輯為：從后往前依次進行比較，如果待插入元素大于當前元素，則將待插入元素插入到當前元素的后一位，如果待插入元素小于當前元素，則將當前元素后移一位。不斷重復該過程直至到數(shù)組的最后一位

其實現(xiàn)的具體代碼為：

def insertion_sort(a):
 length = len(a)
 if length <=1:
  return 
 for i in range(1,length):
  j = i-1
  value = a[i]
  while j >=0:
   if a[j]<value:
    a[j+1] = value
    break
   else:
    a[j+1] = a[j]
    if j == 0:
     a[j] = value 
   j -=1
  print(a)

    return a時間復雜計算為：我們需要將整個數(shù)組遍歷一遍，所以這一部分為O(n)，在每一次遍歷中都要執(zhí)行一次插入操作，其時間復雜度為O(n)，所以總時間復雜度為O(n2)

選擇排序

選擇排序跟插入排序算法類似，都是將數(shù)組分為有序區(qū)間和未排序區(qū)間，區(qū)別在于插入排序是將一個新元素插入到有序區(qū)間內(nèi)，而選擇排序則是在未排序區(qū)間中找到最小元素，并交換到有序區(qū)間之后。

實現(xiàn)代碼為：

def selection_sort(a):
 length = len(a)
 if length <=1:
  return
 for i in range(0,length-1):
  min_value = a[i]
  min_index = i
  j = i+1
  while j<length:
   if a[j] < min_value:
    min_value = a[j]
    min_index = j
   j += 1
  a[i],a[min_index] = a[min_index],a[i]

    return a時間復雜度計算：數(shù)組長度為n，一共需要尋找n次最小值，每次尋找最小值都要遍歷未排序區(qū)間一次，其時間復雜度為O(n)，乘以n次為O(n2)

以上是“如何使用Python實現(xiàn)插入排序和選擇排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關知識，歡迎關注億速云行業(yè)資訊頻道！