插入排序算法的原理是将元素一个个插入它应有的顺序里。如果原先顺序为【1,2,4,5】,现在要将3加入排序,那么,实现的步骤是这样的:
【1,2,4,5,3】
【1,2,4,5,5】
【1,2,4,4,5】
【1,2,3,4,5】
实际的排序算法是从左侧的第二位开始,与第一位比较排序。将这个排好序的部分算作一个小文件,之后不断的扩大这个文件,将新加入的元素加入这个文件的顺序位置。直至该文件扩大到整个文件,这个排序就算好了。
以下是python代码实现:
#!/usr/bin/env python
def insertSort(array,begin,end):
if end > begin >= 0:
for i in range(begin+1,end):
temp = array[i]
while (i-1 >=begin) & (array[i-1]>temp):
array[i]=array[i-1]
i -= 1
array[i]=temp
print array
if __name__=="__main__":
array= [4,6,1,3,8,3]
insertSort(array,0,len(array))
print array