淺談插入排序算法在Python程序中的實現(xiàn)及簡單改進(jìn)

這篇文章主要介紹了插入排序算法在Python程序中的實現(xiàn)及簡單改進(jìn),插入排序算法的最差時間復(fù)雜度為O(n^2),最優(yōu)時間復(fù)雜度為O(n),存在一定的優(yōu)化空間,需要的朋友可以參考下

Python實現(xiàn)插入排序的一般范例為：    
#coding=cp936
#coding=cp936
#插入排序算法
def InsertionSort(A):
  for j in range(1,len(A)):
    key = A[j]
    i = j-1
    #向前查找插入位置
    while i>=0 and A[i]>key:
      A[i+1] = A[i]
      i = i-1
    A[i+1] = key
 
#初始化輸入數(shù)據(jù)
A = []
input = raw_input('please input some numbers:') #輸入逗號分隔整數(shù)列 如：7，6，5，1，8，34
for item in input.split(','):
  A.append(int(item))
 
InsertionSort(A)#插入排序
print A

插入算法的原理是：當(dāng)前元素和已經(jīng)排序好的部分比較，滿足條件時插入，插入點之后的元素全部往后移。
然而，我也正是受這個描述的誤導(dǎo)，在實現(xiàn)的時候走了一些彎路。比如有以下列表：    
test = [2, 5, 11, 21, 10, 18, 24]

比如當(dāng)前元素是10，我在開最初的實現(xiàn)思路是從列表的第一個元素開始，一直比較到元素11才找到合適位置.這樣做最終是可以實現(xiàn)排序的，但是有一個問題，就是當(dāng)我把10插入11的位置之后，11和21都需要往后移，這又需要另一個循環(huán)，實現(xiàn)如下：    
def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = 0
    while j < i:
      if sort_list[j] > key:
        for k in range(i,j,-1):
          sort_list[k] = sort_list[k-1]
        sort_list[j] = key
        break
      j += 1
  return sort_list

   首先，引入了三個循環(huán)變量以及三層循環(huán)，效率較低；其次是代碼結(jié)構(gòu)會比較混亂，需要改進(jìn)。

后來我想能不能比較完一個元素就把它移到合適的位置，好如去超市買水果，手里拿到不合適的，總會直接把它放到一邊，不會再碰它。具體到算法實現(xiàn)，還用上面的列表舉例，當(dāng)前元素是10，先跟相鄰的21比較，發(fā)現(xiàn)21比10大，則21往后移動一位，即移到10所在位置；然后10和11比較，又會把11往后移動一位；在比較到元素5時，發(fā)現(xiàn)已經(jīng)找到了10應(yīng)該存放的位置，而此時移動也隨之完成。
代碼實現(xiàn)如下：    
def insertSort(sort_list):
  list_length = len(sort_list)
  if list_length < 2 :
    return sort_list
  for i in range(1,list_length):
    key = sort_list[i]
    j = i - 1
    while j >=0 and sort_list[j] > key:
      sort_list[j+1] = sort_list[j]
      j -= 1
    sort_list[j+1] = key
  return sort_list

   孰優(yōu)孰劣，大家對比便知。