插入排序

插入排序和选择排序类似, 也是在每个数组元素左边的数据都是有序的, 但是不确定他们的最终位置在哪里. 都是排序完的结果都是升序, 但是选择排序是将每个数据向后比较, 上次的比较和交换结果对下次的比较交换并没有什么影响. 而插入排序就不一样了, 插入排序是向前比较, 而它前面的数据是已经排序好了的. 因此插入排序的结果是受数据输入的影响的.如果输入的数据是一个已经排序好的数组, 那么插入排序的时间复杂度仅仅是`O(N)`. 更多关于性能方面的介绍我会在最后给出, 下面我们看一个实现, 以及对一组简单数据排序后的结果:

#-*- coding=utf-8 -*-

data = [10, 2, 5, 3, 6, 4]
print data

def sort():
    for i in range(0, len(data)):
        for j in range(i, 0, -1):
            if data[j] < data[j - 1]:
                tmp = data[j - 1]
                data[j - 1] = data[j]
                data[j] = tmp
                
            

sort()

结果为

[10, 2, 5, 3, 6, 4]
2 compore 10 -> [2, 10, 5, 3, 6, 4]
5 compore 10 -> [2, 5, 10, 3, 6, 4]
2 compore 5 -> [2, 5, 10, 3, 6, 4]
3 compore 10 -> [2, 5, 3, 10, 6, 4]
3 compore 5 -> [2, 3, 5, 10, 6, 4]
2 compore 3 -> [2, 3, 5, 10, 6, 4]
6 compore 10 -> [2, 3, 5, 6, 10, 4]
5 compore 6 -> [2, 3, 5, 6, 10, 4]
3 compore 5 -> [2, 3, 5, 6, 10, 4]
2 compore 3 -> [2, 3, 5, 6, 10, 4]
4 compore 10 -> [2, 3, 5, 6, 4, 10]
4 compore 6 -> [2, 3, 5, 4, 6, 10]
4 compore 5 -> [2, 3, 4, 5, 6, 10]
3 compore 4 -> [2, 3, 4, 5, 6, 10]
2 compore 3 -> [2, 3, 4, 5, 6, 10]