---恢复内容开始---

插入排序

经典显示（参照算法导论）

一副扑克牌放在桌面上 花色朝下，每次从桌面上拿去最上面的一张 ，放入自己手中的牌中的正确位置，（每次都是对手中的牌排序，并且每次拿去桌面上的牌时，手中的牌已经排序好，当桌上的牌没有时，所有的排序都已经排序好.   其中注意点：将后面一张牌与前一张比如果小于就交换位置。 办法二 【最佳方法】将最后一张牌与 for循环下面的每个元素比A[i]，若小于就向后移一位A[i+1] = A[i], 但是刚拿过的牌 j 必须要付给一个临时变量来保存其中的值。否则会被前面的一位给覆盖掉。再讲tmp放入合适位置）

术语： 

循环不变式：手中已经排好序的A[1 .... j-1]表示循环不变式

循环不变式：在循环过程中的状态值：

初始化：内循环的之前为真，即 循环第一次迭代之前为真                 证明 a[i]为a[0],只有一个元素。故为真

保持：如果循环的某次迭代之前为真 ，那么 下次迭代之前，它仍为真   证明 假设 a[1 ... j-1 ]为真， 下一个插入元素找到合适位置，故a[1 .... j]也为真

终止：当循环终止时，不变式为仍为真　　　　　　　　　　　　　　　证明 终止条件 j>A.length 终止时 已经排好序 故为真  保持真确

核心模板

insertion-sort(A)　　　　　　　　　　　　　　　　　　　　　　　　代价      次数

for 2 to A.length　　　　　　　　　　　　　　　　　　　　　　      c1　　 　 n

　　key=A[j]　　　　　　　　　　　　　　　　　　　　　　　　　　 c2           n-1

　　//insett A[j] into the sorted sequence A[1 ...... j-1]　　　　

　　// 插入A[j]到已经排好序的序列A[1 .... j-1]

　　i = j- i　　　　　　　　　　　　　　　　　　　　　　　　　　　  c3           n -1

　　while i>0 and A[j]>key　　　　　　　　　　　　　　　　　　　 c4           2+3+4+5+.......+n = n(n+1)/2-1

　　　　A[i+1] = A[i]　　　　　　　　　　　　　　　　　　　　　　 c5           2+3+4+.......+n-1 = n(n-1)/2

　　　　i = i - 1　　　　　　　　　　　　　　　　　　　　　　　　　c6            n(n-1)/2

　　A[i+1] = key　　　　　　　　　　　　　　　　　　　　　　　　 c7            n-1

Java核心代码

//

for（int i=0; i<a.length; i++）{

　　//对前 i 张进行排序，每次内循环中 i 的值是不变的

　　for(int j=i-1; j>0; i--){

　　　　if(a[j+1]<a[j]){  //第一个j+交换1 的值就是a[i] 的值 每次都和前一个作比较 如果小于 就交换

　　　　　　swap(i,j);

　　　　}else{

　　　　　　break;　　

　　　　}

　　}

}

public void swap(int i,int j){

　　int tmp = a[j];

　　a[j] = a[i];

　　a[i] = a[j];

}

//正确的

for（int i=0; i<a.length; i++）{

　　//对前 i 张进行排序，每次内循环中 i 的值是不变的

　　int tmp = a[i]

　　int j= i-1;

　　for(j; j>0; j--){

　　　　if(a[j]>tmp){

　　　　　　a[j+1] = a[j];

　　　　}else{

　　　　　　a[j+1] = tmp;

　　　　}

　　}

}

分析算法 ：分析运行时间（影响 运行性能的因素：规模， 以及已排序程度 ）

　　　　如上图 模板中的运行时将总和

　　T(n)= c1n + c2(n-1) + c3(n-1) + c4(n(n+1)/2-1)  + c5(n(n-1)/2)  + c6(n(n-1)/2) +c7（n-1)

　　　　=(c4 + c5 + c6 )n*2 +  (c1 + c2 + c3 + c4/2 - c5/2 - c6/2 +c7)n - (c2 + c3 + c4 + c5)

　　最好情况  a[i]>a[j].   所以 对于while 循环体内 只执行一次  c4

     故 T(n) =  (c1 + c 2 + c3 + c4 + c7)n - (c2 + c3 + c4 +c8) 为线性函数 故时将复杂度相当于 O(n)[读作 theta n ]

　　最坏情况： 倒序 （算法运行的最长时间）【最坏情况。数据库中对缺失信息的检索。最坏情况就会出现。所以在数据库中就会经常出现最坏情况】

　　平均情况：平均情况 往往与最坏情况 大致一致 。往往都是同种性质的同种维度的 增量函数

时间复杂度: 【参照 xingoo博客】

如果排序的数组是正序的，那么时间复杂度相当于O(n)，

而如果排序是随机的，时间复杂度相当于O(n^2/4).

倒置的时间复杂度是最高的，O(n^2).

插入排序 Insertion-sort