|
哨兵的作用 算法中引进的附加记录R[]称监视哨或哨兵(Sentinel) 哨兵有两个作用 ① 进人查找(插入位置)循环之前它保存了R[i]的副本使不致于因记录后移而丢失R[i]的内容; ② 它的主要作用是在查找循环中监视下标变量j是否越界一旦越界(即j=)因为R[]key和自己比较循环判定条件 不成立使得查找循环结束从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件j>=) 注意 ① 实际上一切为简化边界条件而引入的附加结点(元素)均可称为哨兵 【例】单链表中的头结点实际上是一个哨兵 ② 引入哨兵后使得测试查找循环条件的时间大约减少了一半所以对于记录数较大的文件节约的时间就相当可观对于类似于 排序这样使用频率非常高的算法要尽可能地减少其运行时间所以不能把上述算法中的哨兵视为雕虫小技而应该深刻理解并掌握 这种技巧 给定输入实例的排序过程 设待排序的文件有个记录其关键字分别为 为了区别两个相同的关键字后一个 的下方加了一下划线以示区别其排序过程见【 动画模拟演示 】 算法分析 算法的时间性能分析 对于具有n个记录的文件要进行n趟排序 各种状态下的时间复杂度 注意 初始文件按关键字递增有序简称正序 初始文件按关键字递减有序简称反序 算法的空间复杂度分析 算法所需的辅助空间是一个监视哨辅助空间复杂度S(n)=O()是一个就地排序 直接插入排序的稳定性 直接插入排序是稳定的排序方法 |
