InsertionSort

算法形式

插入排序类似于摸牌的时候人们整理牌的过程，摸牌结束时，手中的牌就是排序好的
伪代码：

IMSERTION_SORT(A)//对数组A进行插入升序排序
for j = 2 to A.length
	key = A[j]
	//将A[j]插入已排序好的A[1..j-1]
	i = j - 1
	while i > 0 and A[i] > key
		A[i+1] = A[i]
		i = i - 1
	A[i+1] = key//将正在排序的元素插入适当的位置

算法证明

A[1..j-1]就是原来1到j-1的元素，且已经按序排好，把这种形式地表示为一个循环不变式，它能证明算法的正确性

初始化：首先在循环迭代开始前（j=2），子数组A[1..j-1]就是由单个数字组成，显然循环不变式成立
保持：for循环将A[j-1]、A[j-2]、A[j-3]向右移动一个位置，直到A[j]找到合适的位置，最后将其插入
终止：循环终止条件：j>A.length,显然此时j=A.length+1,带入循环不变式得，A[1..A.length]以按序排列，该不变式即表示整个数组，验证了算法的正确性

算法分析

每行语句的运行成本是由该语句运行一次的成本和运行次数决定的
设n=A.length,单次运行成本为$C_i$,$t_j$表示对j执行while循环的次数，因为该值和输入数据的形式相关，所以他是不确定的

例如第二行for循环的单次运行成本为c$_1$,次数为n-1,则该行的的运行成本为c$_1$*(n-1)，对于while循环为:$c_4$($\sum_{j=2}^n t_j$)

当我们考虑输入数据已经排好序了，即最佳情况时，while循环只进行一次，而内部操作则为零次
最终总时间为$T(n)=(c_1+c_2+c_3+c_4+C_7)n-(c_2+c_3+c_4+c_7)$,将语句代价$c_i$抽象为常量a,b等，则运行时间可表示为$T(n)=an+b$,它是n的线性函数

如果数组是反向排序，即遇到了最坏的情况，此时上文设置的$t_j=j$,所有最终结果为$T(n)=an^2+bn+c$,是n的二次函数

源代码

python
C++