是对少量元素有效的排序算法。（效率上） 排序原理，类似于打牌时在手上拿牌，把牌放到正确的位置1。 参数：需要排序的数组。 原地（原址）算法，在算法执行过程中，只使用常数个存储空间（和问题规模不相关）。 在算法结束时，输入数组包含排序好的输出序列。 Python代码：
#flag代表那升序还是降序排序，true代表升序 def InsertionSort(l, flag=True): for i in range(1, len(l)): key = l[i] for j in range(i - 1, -1, -1): if l[j] > key: l[j + 1] = l[j] else: break l[j + 1] = key if not flag: l.reverse()详见算法导论P10。 这里对循环不变式做一个说明和总结： 循环不变式是一个“性质”，其在算法的初始化、保持和终止阶段都可被证明为真或为假。由此证明算法正确性。 在初始化和保持阶段，循环不变式的证明类似于数学归纳法，在终止阶段，终止这种归纳，联合终止条件，证明算法正确性。 实际上，循环不变式就是说，在算法中存在这么一个性质，其从算法的开始保持到终止，若其一直保持，结合终止条件，则可得到结论，算法达成其目标。 针对插排的证明见算法导论P11。 伪代码约定：算法导论P11。
2.1-3：已遍历比较的序列中，没有值等于v的元素。
分析算法的结果意味着预测算法需要的资源。通常度量计算时间。这个度量一般考虑的是单处理器，没有并发性。 算法导论书中不讨论对真实计算机中指令运行所用的时间和RAM的建模问题。
插入排序所需的时间依赖于：输入，输入数组被排序的程度。 通常一个程序运行的时间被描述成输入规模的函数。
其最佳概念依赖于研究的问题。也就是说，对于不同的问题，无法给出一个统一的概念。可以认为，输入中某一个量的增长会导致算法计算步骤增长的，这个量就是输入规模，例如排序算法的数组长度
执行的基本操作或步数。步是一个抽象概念，以独立于具体的机器。书中假设执行每行伪代码需要常数时间（也就是不随输入规模而改变）。
算法导论P14 注意，其中 tj 表示对于值jwhile2循环执的次数。 由于 tj 的值依赖于输入的有序性，故在输入不确定的情况下无法完全的分析算法运行时间（只能做统计分析）。书中给出了其最好运行时间： an+b 和最坏运行时间 an2+bn+c ，其中a, b, c是常数，其依赖于语句代价常数。
算法往往分析最坏情况，理由如下：
其给出了任何输入的运行时间的上界。对一些算法最坏情况经常出现。平均情况往往与最坏情况一样差。平均情况往往是基于概率分析技术的，是一个期望运行时间。
忽略运行时间中不重要的项，记插入排序的最坏运行时间为 Θ(n2) 。这是一个增长量级的定义，也就是说，存在足够大的n使得 Θ(n3) 的算法运行时间一定大于 Θ(n2) 的算法运行时间。 在后续的章节会给出 Θ 的精确定义。
算法设计技术有很多，插排用的是增量方法。
思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后再合并这些子问题的解，再来建立原问题的解。 分支模式在每层递归时都有3个步骤：
分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。解决这些子问题，递归地求解各子问题。若子问题规模足够小，则直接求解。合并这些子问题的解成原问题的解。归并排序：
分解：将当前区间一分为二，即求分裂点 mid = (low + high)/2; 求解：递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。合并：将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。算法如下图:
伪代码见算法导论P17。 其主要由两个函数组成，一个是分解的，一个是归并的。写一下就全清楚了。
分治法常有：
T(n)={Θ(1)aT(n/b)+D(n)+C(n)n≤cn>1 其中， Θ(1) 是问题规模足够小时使用常量时间可求得解。 aT(n/b) 是对a个子问题求解的时间，每一个子问题规模是 n/b 。分解问题需要时间 D(n) ，合并需要 C(n) 。 对于归并排序： T(n)={Θ(1)2T(n/2)+Θ(n)n=1n>1 分解需要常数时间，归并时间是 Θ(n) 。第四章会使用 主定理来证明 T(n)=Θ(nlgn) 。 简单证明见算法导论P21。（特殊情况）2.3-7 先排序，后二分
