python插入排序

插入排序的主要思想就是：
每次取得一个列表元素，与已排序好的列表进行比较，然后插入相应的位置，最终获得排序好的列表。
意思是这样的：
一个未排序的列表：
下标： 0 1 2 3 4
数组：[5,4,3,2,1]
我们把列表分成两个部分seqOK,seqNo（只是在一个列表中划分成两个部分，而不是截取成两个列表），已排序好(seqOK)和未排序好(seqNo)的列表。
我们认为列表的第一个元素是已经排序好的，只要一个元素嘛，还想怎么排？余下的部分是未排序好的列表。
使用未排序的列表(seqNo)中的第一个元素 a ，对比已经排序好的列表(seqNo)中的每一个元素，从后往前对比。如果 seqOk[i] > a，则对比排序好的列表seqOK中的下一个 seqOk[i-1]。直到seqOk[i] < a的时候 将a插入当前位置。
依次seqNo中的每一个元素，最终获得排序好的列表。

算法导论中的 排序算法 实现如下：
代码如下：

    seq = [5, 4, 0, 3, 2, 1]
    print '排序前: ',seq
    for i in range(1,len(seq)):
        temp = seq[i]
        index = i-1
        while index >= 0 and seq[index] > temp:
            seq[index+1] = seq[index]
            index -= 1
        seq[index+1] = temp
        print '第 %s 次排序后' %i ,seq
    print '排序后：',seq```
运行结果如下：
![image.png](https://img.haomeiwen.com/i4131789/67f98a9f34c79eb5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
还有一种实现方式如下：

seq = [5, 4, 0, 3, 2, 1]
print '排序前: ', seq
for i in range(1,len(seq)):
    temp = seq.pop(i)
    index = i-1
    while index > 0 and seq[index]>temp:
        index -= 1
    #这个地方需要判断一次
    if index == 0 and temp > seq[index]:
        index += 1
    seq.insert(index,temp)
    print '第 %s 次排序后' % i, seq
print '排序后：', seq

运行结果如下：
![image.png](https://img.haomeiwen.com/i4131789/1f2cdb0a6d275747.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
代码中为什么需要判断一次呢？
例如：[5, 4, 0, 3, 2, 1]
第一次循环的时候 i == 1 也就 temp == 4，index == 0，因为index == 0 所有while根本就没有执行，也就是说 seq[index]>temp根本就没有比较就直接把元素插入index前面，也就是 把4 插入到 5的前面。
当列表排序为 [0,4,5,3,2,1]的时候：
此时 i == 3 也就是 temp == 3, index==2。依次比较：seq[index]>temp
第一次：index == 2 ，5>3 则 index -= 1。
第二次：index == 1， 4>3 则 index -= 1。
第三次：index == 0，但是 while index>0 不成立，所以 seq[index]>temp也就是0>3并没有进行比较。
循环结束：此时index == 0 ，seq.insert(index,temp）将3插入下标index 0之前。
所以排序后的结果为： [3,0,4,5,2,1]
所以在插入之前要判断一下是不是到达第一个元素了 也就是下标index == 0的时候 如果：temp > seq[index]，则插入index的后面，而不是前面。
也就是说 当index==0的时候，此时 temp == 3，seq[index] == 0,这时候3要插入到0的后面，插入前面就错了。
代码如下：

seq = [5, 4,0,3, 2, 1]
print '排序前: ', seq
for i in range(1,len(seq)):
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
seq.insert(index,temp)
print '第 %s 次排序后' % i, seq
print '排序后：', seq

运行结果如下：
![image.png](https://img.haomeiwen.com/i4131789/ed13d3966a82105a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

我们对比一下 两种排序方式：
第一种：每次对比都把符合条件的元素后移一位。

    while index >= 0 and seq[index] > temp:
        seq[index+1] = seq[index]
        index -= 1

第二种：每次循环只需要弹出元素一次，插入元素一次。弹出，插入时数据结构的变化是python帮我们维护的，可能比我们手动来维护性能高一些吧。

    temp = seq.pop(i)
    index = i-1
    while index > 0 and seq[index]>temp:
        index -= 1
    if index == 0 and temp > seq[index]:
        index += 1
    seq.insert(index,temp)

我们来对比一下运行时间：

def haoshi(func):
def wapper():
start_time = time.time()
func()
print func.name,'耗时 ',time.time()-start_time
return wapper

@haoshi
def charu1():
"""第一种种排序插入方式"""
seq = range(10000)[::-1]
for i in range(1,len(seq)):
temp = seq[i]
index = i-1
while index >= 0 and seq[index] > temp:
seq[index+1] = seq[index]
index -= 1
seq[index+1] = temp

@haoshi
def charu2():
"""第二种排序插入方式"""
seq = range(10000)[::-1]
for i in range(1,len(seq)):
temp = seq.pop(i)
index = i-1
while index > 0 and seq[index]>temp:
index -= 1
if index == 0 and temp > seq[index]:
index += 1
seq.insert(index,temp)

charu1()
charu2()

运行结果如下：
![image.png](https://img.haomeiwen.com/i4131789/668f005de848b0b7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)