python插入排序_用Python實作排序算法——插入排序

本文用python實作插入算法。插入算法的原理是：目前元素和已經排序好的部分比較，滿足條件時插入，插入點之後的元素全部往後移。然而，我也正是受這個描述的誤導，在實作的時候走了一些彎路。比如有以下清單：

test = [2, 5, 11, 21, 10, 18, 24]

比如目前元素是10，我在開最初的實作思路是從清單的第一個元素開始，一直比較到元素11才找到合适位置.這樣做最終是可以實作排序的，但是有一個問題，就是當我把10插入11的位置之後，11和21都需要往後移，這又需要另一個循環，實作如下：

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

首先，引入了三個循環變量以及三層循環，效率較低；其次是代碼結構會比較混亂，需要改進。

後來我想能不能比較完一個元素就把它移到合适的位置，好如去超市買水果，手裡拿到不合适的，總會直接把它放到一邊，不會再碰它。具體到算法實作，還用上面的清單舉例，目前元素是10，先跟相鄰的21比較，發現21比10大，則21往後移動一位，即移到10所在位置；然後10和11比較，又會把11往後移動一位；在比較到元素5時，發現已經找到了10應該存放的位置，而此時移動也随之完成。

代碼實作如下：

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

孰優孰劣，大家對比便知。