直接插入排序时间分析 最好的情况(关踺字在记录序列中顺序有序): “比较”的次数: “移动”的次数 最坏的情况(关键字在记录序列中逆序有序): 比较”的次数: “移动”的次数 ∑(+2 n-1)n+4) 总的平均比较和移动次数约为 ∑(2+2+2)=2从1(n-1(n+4=O(n2
11 最好的情况（关键字在记录序列中顺序有序）： “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： “比较”的次数： 1 1 1 1 = − − = n n i 2(n-1) “移动”的次数： “移动”的次数： 2 ( 1) 1 1 − = − = n n i n i 2 ( 1)( 4) ( 2) 1 1 − + + = − = n n i n i 总的平均比较和移动次数约为 ( ) 2 ( 1)( 4) 2) ( 2) 2 2 ( 2 1 1 1 1 O n n n i i i n i n i = − + + + = + = − = − = 直接插入排序时间分析
10.22折半插入排序 主要思想 当第+1个记录要插入前i个有序记录序列时 可利用折半査找方式确定插入位置,以减少 比较次数 12
12 10.2.2 折半插入排序 • 主要思想 • 当第i+1个记录要插入前i个有序记录序列时， 可利用折半查找方式确定插入位置，以减少 比较次数
折半插入排序 例如: 插入 位置!1 14364952805861239775 high low 再如:/插入 m 位置 14364952586180239775 1gh low
13 i low high m m low low m high i low high m high m high m low 例如: 再如: 插入 位置 插入 位置 14 36 49 52 80 58 61 23 97 75 14 36 49 52 58 61 80 23 97 75 折半插入排序
折半插入排序 ⅴ。id工 nsertsort1( RecType R[],intn) t int i,3,low,high, mid; Recfype tmp; for(i=1;i<n;i+十) tmp=R[i]i //将R[i]保存到tmp中 1。w=0;high=i-1; while(1ow<=high)//在R[1ow.high]中查找插入的位置 mid=(lowthigh)/2; //取中间位置 if (tmp key<R[mid] key) high=mid-li //插入点在左半区 else low=mid+1 //插入点在右半区 f。x(j=i-1;>=high+1;--) //记录后移 R[j+1]=R[j]; Thigh+1]=tmp; //插入 14
14 折半插入排序 void InsertSort1(RecType R[],int n) { int i,j,low,high,mid; RecType tmp; for (i=1;i<n;i++) { tmp=R[i]; //将R[i]保存到tmp中 low=0;high=i-1; while (low<=high) //在R[low..high]中查找插入的位置 { mid=(low+high)/2; //取中间位置 if (tmp.key<R[mid].key) high=mid-1; //插入点在左半区 else low=mid+1; //插入点在右半区 } for (j=i-1;j>=high+1;j--) //记录后移 R[j+1]=R[j]; R[high+1]=tmp; //插入 } }
1023希尔排序 ◆从“减小n”和“基本有序”两方面对直接插入排 序进行改进,是一种分组插入方法。 ◆基本思想: ◆先取定一个小于n的整数d作为第一个增量,把表 的全部记录分成d个组,所有距离为d1的倍数的记录 放在同一个组中,在各组内进行直接插入排序; ◆然后,取第二个增量d2(<d1),重复上述的分组和 排序,直至所取的增量d=1(d4<d1d2<d1),即所有 记录放在同一组中进行直接插入排序为止。 15
15 从“减小n”和“基本有序”两方面对直接插入排 序进行改进，是一种分组插入方法。 基本思想： 先取定一个小于n的整数d1作为第一个增量，把表 的全部记录分成d1个组，所有距离为d1的倍数的记录 放在同一个组中，在各组内进行直接插入排序； 然后，取第二个增量d2 (＜d1 )，重复上述的分组和 排序，直至所取的增量dt =1(dt<dt-1<…<d2<d1 )，即所有 记录放在同一组中进行直接插入排序为止。 10.2.3 希尔排序