插入排序算法

插入排序包含两种，一种是直接插入排序，另一种是希尔排序算法。直接插入排序适用于小数据或者基本有序的数组，而希尔排序适合较大数据量。
在生活中，我们要对书籍或者档案按编号排序，经常采用插入排序的方法。
1、直接插入排序
基本思想：把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
源码：

#coding:utf-8
def sort(origin_lis):
    """
    插入排序算法
    适用于小数据和数组基本有序的
    :param origin_lis: 排序的原始数组
    :return:
    """
    for i in range(1, len(origin_lis)):
        # 保存待插入的元素值
        temp = origin_lis[i]
        # 记录开始比较的下标
        j = i - 1
        # 遍历待插入元素左边的值，找到合适位置插入
        while j > -1 and origin_lis[j] > temp:
            origin_lis[j + 1] = origin_lis[j]
            j -= 1
        origin_lis[j + 1] = temp
    return origin_lis

if __name__ == '__main__':
    print sort([4,2,3,5,12,13,7,555,4,5,8,2,1,4,7])

2、希尔排序
它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序实质上是一种分组插入方法。
基本思想：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
一般gap按 数列长度多次减半得到

源码：

#coding:utf-8
def sort(origin_lis, increment):
    """
    希尔插入排序算法，适合大数据量数列
    :param origin_lis: 排序的原始数组
    :param increment : 步长
    :return:
    """
    for i in range(increment, len(origin_lis)):
        # 保存待插入的元素值
        temp = origin_lis[i]
        # 记录开始比较的下标
        j = i - increment
        while j > -1 and origin_lis[j] > temp:
            origin_lis[j + increment] = origin_lis[j]
            j -= increment
        origin_lis[j + increment] = temp

if __name__ == '__main__':
    lis = [2, 3, 5, 12, 13, 7, 555, 4, 5, 8, 2, 1, 4, 7]
    increment = len(lis) / 2
    while increment > 0:
        sort(lis, increment)
        increment /= 2
    print lis

希尔排序的sort和直接插入排序的sort代码基本一致