∑(bog2{」+1)=!+2+2+3+…+3+ +4+∵+4+·十k++k= (1+2+22+…+2k-)+(2+22+…+2k-)+ +(22+…+2)+ +2 kk k ∑∑2=∑2-(1+2+…+2-) k k k ∑2(2 k-i+1 ∑2-∑2 k. 2-(2-1)=nlog n-n+la n log n
( ) k n n n n n k k i k k k i i k i k i k k i i k i i k i k i k j i j k k k k n i k 2 2 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 2 1 2 2 2 2 2 1 1 2 2 (2 1) log 1 log 2 (2 1) 2 2 2 2 (1 2 2 ) (2 2 ) 2 (1 2 2 2 ) (2 2 2 ) 4 4 log 1 1 2 2 3 3 3 1 0 1 2 = − − = − + = − = − = = = + + + = + + + + + = = + + + + + + + + + + + + + + + + = + = + + + + + + = − = − + = − = − − = = − − − − − − = −
当n较大时,总关键码比较次数比直接插入 排序的最坏情况要好得多,但比其最好情况 要差 在对象的初始排列已经按关键码排好序或接 近有序时,直接插入排序比对分插入排序执 行的关键码比较次数要少。对分插入排序的 对象移动次数与直接插入排序相同,依赖于 对象的初始排列。 对分插入排序是一个稳定的排序方法
当 n 较大时，总关键码比较次数比直接插入 排序的最坏情况要好得多，但比其最好情况 要差。 在对象的初始排列已经按关键码排好序或接 近有序时，直接插入排序比对分插入排序执 行的关键码比较次数要少。对分插入排序的 对象移动次数与直接插入排序相同，依赖于 对象的初始排列。 对分插入排序是一个稳定的排序方法
链表插入排序 链表插入排序的基本思想是:在每个对象的结 点中增加一个链接指针数据成员link。 对于存放于数组中的一组对象v1,p12],,,vm 若ν1lⅥ12l,…,vl已经通过指针link,按其关 键码的大小,从小到大链接起来,现在要插入 v引,i=2,3,…,n,则必须在前面1个链接起来 的对象当中,循链顺序检测比较,找到引应插 入(或链入)的位置,把ν插入,并修改相应的 链接指针。这样就可得到v1l12,…,yd的一 个通过链接指针排列好的链表。 如此重复执行,直到把v团也插入到链表中排好 序为止
链表插入排序 链表插入排序的基本思想是：在每个对象的结 点中增加一个链接指针数据成员link。 对于存放于数组中的一组对象V[1], V[2], …, v[n]， 若v[1], V[2], …, v[i-1]已经通过指针link，按其关 键码的大小，从小到大链接起来，现在要插入 v[i], i = 2, 3, …, n，则必须在前面i-1个链接起来 的对象当中，循链顺序检测比较，找到v[i]应插 入(或链入)的位置，把v[i]插入，并修改相应的 链接指针。这样就可得到v[1], V[2], …, v[i]的一 个通过链接指针排列好的链表。 如此重复执行，直到把v[n]也插入到链表中排好 序为止
25 49 25 ) 08 0 2 3 5 6 i=2 current pre I i=3 [一 current pre i=4的 pre current
25 49 25* 16 08 0 1 2 3 4 5 6 i = 2 i = 3 21 初始 current pre i current pre i pre current i i = 4
25 49 25 ) 08 0 2 3 5 6 i=5 pre current 国的 current i 结果[
25 49 25* 16 08 0 1 2 3 4 5 6 i = 5 i = 6 21 pre current i 结果 pre current i