插入排序

插入排序的来源

在一个序列已经有序的情况下，想在序列号中插入一个数，且插入后依旧有序。这个时候可以用插入排序

插入排序的基本思想

每一步将待排序的值，按其值与已经排好序的序列比较大小，然后插入合适的位置。

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]