插入排序的来源
在一个序列已经有序的情况下，想在序列号中插入一个数，且插入后依旧有序。这个时候可以用插入排序
插入排序的基本思想
每一步将待排序的值，按其值与已经排好序的序列比较大小，然后插入合适的位置。
python代码实现
#!/usr/bin/python
# encoding: utf-8
# 插入排序
def insertSort(alist):
# 迭代的次数
for i in range(1,len(alist)):
# 从序列中的第二个数作为待排序的数
flag = alist[i]
# 待排序的数与排好的序列 从后往前一次比较
for j in range(i,0,-1):
# 若小于序列中的数，则交换位置
if alist[j-1] > alist[j]:
alist[j-1],alist[j] = alist[j], alist[j-1]
elem = [3,5,2,1,6,7,4]
insertSort(elem)
print elem # [1, 2, 3, 4, 5, 6, 7]
折半插入排序
折半插入排序是对直接插入排序的一种优化，在待排序数与已经排好序的序列比较时，不从最后面一次往前面比较，而是从最中间的位置（k/2）比较，若大于这个最中间的数，则取k/2到k之间最中间的数继续比较，最终找到插入的位置。
#!/usr/bin/python
# encoding: utf-8
def halfInsertSort(alist):
# 迭代的次数
for i in range(1, len(alist)):
# 从序列中的第二个数作为待排序的数
flag = alist[i]
low, high = 0, i - 1
# 待排序的数与排好的序列 比较
while low <= high:
# 中间值
mid = (low+high)/2
# 如果小于中间值，
if alist[mid] > flag:
# 则在小于中间值的那部分查找
high = mid-1
# 如果大于中间值
else:
# 则在大于中间值得那部分查找
low = mid+1
# 删除这个位置的值
alist.pop(i)
# 添加flag到找到的位置(这里一定是low的位置，而不是high)
alist.insert(low,flag)
elem = [3, 5, 2, 1, 6, 7, 4]
halfInsertSort(elem)
print elem # [1, 2, 3, 4, 5, 6, 7]
