插入排序算法主要有三种：直接插入排序、折半插入排序、希尔排序
1、直接插入排序：
/**
* 直接插入排序,
* 1、从i-->length-1开始做插入扫描
* 2、初始化一个要插入的元素（1步骤中的）
* 3、从0-->i开始做插入排序操作
* 如果要插入的元素小于0-->i中的某一个元素，则做位置替换，
* 否者，执行第一步（i+1）步骤
* 4、结束
* 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
* 空间复杂度:需要一个空间地址作交换，故O(1);
*/
def StraightInsertionSort(list):
for i in range(1, len(list)): for j in range(i, 0, -1): if list[j] < list[j - 1]: tmp = list[j - 1] list[j - 1] = list[j] list[j] = tmp print list return list2、折半插入排序
/**
* 折半插入排序
* 1、从i-->length-1开始做插入扫描
* 2、初始化一个要插入的元素（1步骤中的）
* 3、从0-->i开始做折半查找插入操作
* a、通过折半的方式定位要插入的元素的位置X
* b、将位置X及以后的元素往后移动一位
* c、将位置X赋值为要插入的元素
* 4、结束
* 时间复杂度:∑(i+1)/2 = (n2+3n+4)/4 =~ n2 ,(1<=i<=n);
* 空间复杂度:需要一个空间地址作交换，故O(1);
*/def BinaryInsertionSort(list):
for i in range(1, len(list)): low = 0 high = i tmp = list[i] while low <= high: mid = (low + high) / 2 if list[mid] > tmp: high = mid - 1 else: low = mid + 1 """this line is special, bucause python‘s list can be get [-2] element""" if i - 1 <= high:continue """find the high tag, then remove j - 1 --> j, last reset index [high + 1] element to tmp""" for j in range(i, high + 1, -1): list[j] = list[j - 1] list[high + 1] = tmp print list return list
3、希尔排序
"""delta = 10 / 2 = 549 38 65 97 26 13 27 49 55 41A 1B 2A 2B 3A 3B 4A 4B 5A 5Bdelta = 5 / 2 = 213 27 49 55 4 49 38 65 97 261A 1B 1C 1D 1E 2A 2B 2C 2D 2Edelta = 2 / 2 = 14 26 13 27 38 49 49 55 97 651A 1B 1C 1D 1E 1F 1G 1H 1I 1Jdelta = 1 / 2 = 04 13 26 27 38 49 49 55 65 97"""def shellSort(list): delta = len(list) while delta / 2 > 0: delta = delta / 2 for i in range(delta, len(list)): tmp = list[i] j = i - delta while j >= 0 and tmp < list[j]: list[j + delta] = list[j] j -= delta list[j + delta] = tmp print list return list
原文：http://www.cnblogs.com/ariesblogs/p/4046633.html