do{/从右向左在有序区R1..i1中查找R[的插 入位置 R+1=Rj;:/将关鍵字大于 Ri. key的记录后移 )while(rio.key<rIil.key) 当R[]key≥ RIJ. key时终止 R[i+1=R|0]; /R插入到正确的位置上 y/lendif 3//Insertsort 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 do{ //从右向左在有序区R[1．．i-1]中查找R[i]的插 入位置 R[j+1]=R[j]； //将关键字大于R[i].key的记录后移 j-- ； }while(R[0].key<R[j].key)； //当R[i].key≥R[j].key时终止 R[j+1]=R[0]； //R[i]插入到正确的位置上 }//endif }//InsertSort
2.哨兵的作用 算法中引进的附加记录R0称监视哨或哨兵 (Sentinel) 哨兵有两个作用: ①进人查找(插入位置)循环之前,它保存 了R印的副本,使不致于因记录后移而丢失R[i 的内容; ②它的主要作用是:在查找循环中“监视” 下标变量是否越界。一旦越界(即j=0),因为 R[0]key和自己比较,循环判定条件不成立使 得查找循环结束,从而避免了在该循环内的每 次均要检测j是否越界(即省略了循环判定条 件"j>=1") 武汉理工大学华 信息工程 系
武汉理工大学华夏学院-信息工程 系 2．哨兵的作用 算法中引进的附加记录R[0]称监视哨或哨兵 (Sentinel)。 哨兵有两个作用： ① 进人查找 (插入位置) 循环之前，它保存 了R[i]的副本，使不致于因记录后移而丢失R[i] 的内容； ② 它的主要作用是：在查找循环中“监视” 下标变量j是否越界。一旦越界 (即j=0)，因为 R[0].key 和自己比较，循环判定条件不成立使 得查找循环结束，从而避免了在该循环内的每 一次均要检测 j是否越界(即省略了循环判定条 件"j>=1")
注意: <心 ①实际上,一切为简化边界条件而引入的 附加结点(元素)均可称为哨兵。 例】单链表中的头结点实际上是一个哨兵 ②引入哨兵后使得测试查找循环条件的时 间大约减少了一半,所以对于记录数较大的文 件节约的时间就相当可观。对于类似于排序这 样使用频率非常高的算法,要尽可能地减少其 运行时间。所以不能把上述算法中的哨兵视为 雕虫小技,而应该深刻理解并掌握这种技巧 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 注意： ① 实际上，一切为简化边界条件而引入的 附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 ② 引入哨兵后使得测试查找循环条件的时 间大约减少了一半，所以对于记录数较大的文 件节约的时间就相当可观。对于类似于排序这 样使用频率非常高的算法，要尽可能地减少其 运行时间。所以不能把上述算法中的哨兵视为 雕虫小技，而应该深刻理解并掌握这种技巧
给定输入实例的排序过程 设待排序的文件有8个记录,其关键字分 别为:49,38,65,97,76,13,27,49。 为了区别两个相同的关键字49,后一个49的 下方加了一下划线以示区别。其排序过程见 3.直接插入排序的稳定性 直接插入排序是稳定的排序方法
武汉理工大学华夏学院-信息工程 系 给定输入实例的排序过程 设待排序的文件有8个记录，其关键字分 别为：49，38，65，97，76，13，27，49。 为了区别两个相同的关键字49，后一个49的 下方加了一下划线以示区别。其排序过程见 3．直接插入排序的稳定性 直接插入排序是稳定的排序方法