插入排序算法
The Insertion Sort
插入排序虽然仍是O(n^2)，但其工作方式稍有不同。它始终在列表的前端维护一个已经排序的列表。然后将每个新的项目”插入”到之前的子列表中，使得已排序好的子列表更大一个项目，下图展示了排序的过程。阴影部分表示算法每次传递的有序子列表。
我们首先假定包含一个项目(位置0)的列表已经排序，从1至n-1的每次排序中，这个当前检查的项目要和已经排序的列表比较。当我们回顾已经排序好的子列表时，我们把更大与插入的项目移到右侧，当我们小于要插入的项目时或者已经排序好列表的末尾时，可以插入当前项目。
下图详细展示了第五个数排序过程。在该算法中，存在已经由17，26，54，77和93组成的五个的排序列表，我们想把31重新插入已经排序好的列表中，第一次和93比较，93>31，导致93右移，77和54也是右移。当遇到26时，这个移动的过程将停止并且31被置于空余的位置。现在我们有了六个项目的排序列表。
排序n个项目需要n-1次，迭代顺序从位置1开始并移动到n-1，因为这些需要插入到已经排序好的列表中，执行移动操作，将列表中的某个值向上移动一个位置，使其后面的可以插入。请记住这并不是之前的算法那样完全交换。
插入排序的比较次数最大是n-1个整数的总和。这时O(n^2)。但是最好的情况是，每次传递都进行一次比较，这将是一个已经排序的列表。
关于转换和交换的一个注意事项，一般，一个转换操作需要交换大约三分之一的时间。在基准研究中，插入排序会显示的效果更好。
代码
def insetSort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17]
insetSort(alist)
print(alist)
从后面依次向前比较。前面是已经排序好的列表，依次将后面的项目插入到前面。
插入排序
一个无序的列表，按照顺序排列。一个元素的话，是有序的，后面的数字依次和前面的排序，慢慢的前面的数字是有顺序的，然后依次进行排序，直到最后。
8 6 2 3 1 5 7 4
6 8 2 3 1 5 7 4
2 6 8 3 1 5 7 4
2 3 6 8 1 5 7 4
1 2 3 6 8 5 7 4
1 2 3 5 6 8 7 4
1 2 3 5 6 7 8 4
1 2 3 4 5 6 7 8
插入排序的第二层可以提前结束的。
代码1
# -*- coding:utf-8 -*-
def InsertSort(a):
n = len(a)
for i in range(1,n):
#前面的元素都是有序排列好的
for j in range(i,0,-1):
#如果比前面的小，则替换位置
if a[j] < a[j-1]:
a[j],a[j-1] = a[j-1],a[j]
#否则比前面所有的元素都大，不需要移动
else:
break
if __name__ == '__main__':
a = [10,4,5,1,2,3,9,8,7]
print("原始列表为: %s" % a)
InsertSort(a)
print("排序后：%s" % a)
结果
C:\Users\Administrator\Desktop\Algo>python2 InsertSort.py
原始列表为: [10, 4, 5, 1, 2, 3, 9, 8, 7]
排序后：[1, 2, 3, 4, 5, 7, 8, 9, 10]
代码2
myList = [2,1,5,3,4,8,7]
#从i=1(第二张牌开始)
for i in range(1,len(myList)):
#要排序的牌
key = myList[i]
#手中左边的牌
j = i - 1
#与 手中的牌逐一比较
while j >= 0 and myList[j] > key:
#满足条件时,交换两张牌的顺序
myList[j+1] = myList[j]
j -= 1
#当不满足时,即该牌比手中所有牌都大,放在最右边
myList[j+1] = key
print(myList)
代码3
和代码2的原理一样，可能这个方便理解一些
# -*- coding:utf-8 -*-
def Insert(a):
for i in range(1,len(a)):
# 寻找元素 a[i]合适插入位置
e = a[i]
# j保存元素e应该插入的位置
j = i;
while(j>0 and a[j-1]>e):
a[j] = a[j-1]
j -= 1
#否则的话，当前值比前面的都大，保存在本地
a[j] = e
return a
if __name__ == '__main__':
a = [10,4,5,1,2,3,9,8,7]
print("原始列表为 %s" % a)
Insert(a)
print("排序列表为 %s" % a)
结果
C:\Users\Administrator\Desktop\Algo>python2 InsertSort3.py
原始列表为 [10, 4, 5, 1, 2, 3, 9, 8, 7]
排序后的列表为 [1, 2, 3, 4, 5, 7, 8, 9, 10]
参考