Python實現插入排序的一般范例為：
#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 #初始化輸入數據A = []input = raw_input('please input some numbers:') #輸入逗號分隔整數列 如：7，6，5，1，8，34for item in input.split(','): A.append(int(item)) InsertionSort(A)#插入排序print A插入算法的原理是：當前元素和已經排序好的部分比較，滿足條件時插入，插入點之后的元素全部往后移。
然而，我也正是受這個描述的誤導，在實現的時候走了一些彎路。比如有以下列表：
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
孰優孰劣，大家對比便知。
新聞熱點
疑難解答
圖片精選
