首页 > 代码库 > 插入排序 Insertion-sort

插入排序 Insertion-sort

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

插入排序

经典显示(参照算法导论)

一副扑克牌放在桌面上 花色朝下,每次从桌面上拿去最上面的一张 ,放入自己手中的牌中的正确位置,(每次都是对手中的牌排序,并且每次拿去桌面上的牌时,手中的牌已经排序好,当桌上的牌没有时,所有的排序都已经排序好.   其中注意点:将后面一张牌与前一张比如果小于就交换位置。 办法二 【最佳方法】将最后一张牌与 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