说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
1、问题
输入 ：由 n 个数构成的一个序列
输出 ：对输入序列的一个排列（重排）使得a1 ' <= a2 ' <= … <= an '
2、伪码
插入排序 算法是一个对少量元素进行排序的有效算法，称为 INSERTION-SORT 。入参为包含了 n 个待排数字的数组 A [ 1 .. n ]，算法输入经 原地排序 （sorted in place，就是说这些数字是在数组 A 中进行重新排序的，在任何时刻，至多只有其中的常数个数字是存储在数组之外的）后，入参数组 A 中就包含了已排好序的输出序列。
插入排序思想：排序的过程其实就是一个起纸牌的过程，即从未排序的序列中取出一个元素，将其插入到已排序序列的正确位置。需要注意的是：循环默认从第二个数开始，因为第1个数不用排序就是已排序的，即属于手里起起来的牌。
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1 .. j - 1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
3、时间复杂度分析
INSERTION-SORT 过程的时间开销与输入长度和已排序程度有关。一般来说，算法所需的时间是与输入规模同步增长的，因而常常将一个程序的运行时间表示为其输入的函数。这里就涉及到两个名词“运行时间”和“输入规模”。
输入规模 的概念与具体问题有关，最自然的度量标准是输入中的元素个数。
算法的 运行时间 是指在特定输入时，所执行的基本操作数（或步数）。这里我们假设每次执行第 i 行所花的时间都是常量 ci 。
首先给出 INSERTION-SORT 过程中，每一条指令的执行时间及执行次数。对 j = 2， 3， …， n ， n = A.length ，设 tj 为第5行 while 循环所做的测试次数。当 for 或 while 循环以通常方式退出时，测试要比循环体多执行1次。另外，假定注释部分不可执行。
该算法总的运行时间是每一条语句执行时间之和。为计算总运行时间 T = [ n ]，对每一对 cost 和 times 之积求和。得：
即使是对给定规模的输入，一个算法的运行时间也可能要依赖于给定的是该规模下的哪种输入。例如，在 INSERTION-SORT 中，如果输入数组已经是排好序的，那就会出现最佳情况。对 j = 2， 3， …， n 中的每一个值，都有 tj = 1，则最佳运行时间为：
T(n) = c1*n + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1) = (c1 + c2 + c4 + c5 + c8)n - (c2 + c4 + c5 + c8)
如果输入数组是按照逆序排序的，那么就会出现最坏情况。我们必须将每个元素 A [ j ]与整个已排序的子数组 A [ 1 .. j - 1 ]中的每一个元素进行比较，因而，对 j = 2， 3， …， n ，有 tj = j 。则最坏运行时间为：
这一最坏情况运行时间可以表示为 a n2 + b n + c ，常量 a ， b 和 c 仍依赖于语句的代价 ci ；因而，这是一个关于 n 的 二次函数 。
4、参考文档
