document.write('对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列；接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。以数组{38，65，97，76，13，27，49}为例(假设要求为升序排列)，直接插入排序具体步骤如下：
第一步插入38以后：[38] 65 97 76 13 27 49
第二步插入65以后：[38 65] 97 76 13 27 49
第三步插入97以后：[38 65 97] 76 13 27 49
第四步插入76以后：[38 65 76 97] 13 27 49
第五步插入13以后：[13 38 65 76 97] 27 49
第六步插入27以后：[13 27 38 65 76 97] 49
第七步插入49以后：[13 27 38 49 65 76 97]
示例代码如下：
def insert_sort(lists):
#插入排序
count=len(lists)
for i in range(1,count):
key=lists[i]
j=i-1
while j＞=0:
if lists[j]＞key:
lists[j+1]=lists[j]
lists[j]=key
j-=1
return lists
if __name__=="__main__":
lists=[3,4,2,8,9,5,1]
print \'排序前序列为:\',
for i in lists:
print i,
print \'\\n排序后结果为:\',
for j in (insert_sort(lists)):
print i,
程序的运行结果为：
排序前序列为：3 4 2 8 9 5 1
排序后结果为：1 2 3 4 5 8 9
插入排序是一种稳定的排序方法，最好情况下的时间复杂度为O(n)，最坏情况下的时间复杂度为O(n2)，平均情况下的时间复杂度为O(n2)。空间复杂度为O(1)。
');