◆算法评价 Ch8 1.trt 0时间复条度 ◆若待排序记录按关键字从小到大排列(正序) 关键字比较次数: 记录移动次数:∑2=2(n-1) ◆若待排序记录按关键字从大到小排列(逆序) 关键字比较次数:>i (n+2)(n-1) 记录移动次数:∑(+1) (n+4)(n-1 ◆若待排序记录是随机的,取平均值 关键字比较次数 4 T(n)=O(n2) 记录移动次数 4 Ch8 1.c
❖算法评价 ⚫时间复杂度 ◆若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 1 1 2 = − = n n i 记录移动次数： 2 2( 1) 2 = − = n n i ◆若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 2 ( 2)( 1) 2 + − = = n n i n i 记录移动次数： 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i ◆若待排序记录是随机的，取平均值 关键字比较次数： 4 2 n 记录移动次数： 4 2 n T(n)=O(n²) Ch8_1.c
★折半插入排序 排序过程:用折半查找方法确定插入位置的排序叫 例 (30)1370853942620 =213(1330)70853942620 76(6133039427085)20 i=820(6133039427085)20 m 1820(433939427085)20 1820(6133939427085)20 s m 1820(6133939427085)20 i=820(613203039427085)
折半插入排序 ❖排序过程：用折半查找方法确定插入位置的排序叫~ 例 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 …... i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s mj i=8 20 (6 13 30 39 42 70 85 ) 20 j s i=8 20 (6 13 20 30 39 42 70 85 )