====== Python实现插入排序 ======
===== 问题描述 =====

将一组随机排列的数字重新按照从小到大的顺序排列。

===== 插入算法 =====


每次从数组中取一个数字，与现有数字比较并插入适当位置。

如此重复，每次均可以保持现有数字按照顺序排列，直到数字取完，即排序成功。

这很像打牌时的抓牌情况，

  * 第一个条件：保持手上的牌的顺序是正确的
  * 第二个条件：每次抓到新的牌均按照顺序插入手上的牌中间。

保证这两条不变，那么无论抓了几张牌，最后手上的牌都是依照顺序排列的。

===== Python 实现 =====

<code python>
#coding=cp936
#coding=cp936
#插入排序算法
def InsertionSort(A):
    for j in range(1,len(A)):
        key = A[j]
        i = j-1
        #向前查找插入位置
        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key
 
#初始化输入数据
A = []
input = raw_input('please input some numbers:') #输入逗号分隔整数列 如：7，6，5，1，8，34
for item in input.split(','):
    A.append(int(item))
 
InsertionSort(A)#插入排序
print A
</code>

===== 参考 =====
http://www.bus836.cn/archives/145