插入排序—直接插入排序(Straight Insertion Sort)

哨兵的作用



算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。

哨兵有两个作用：

① 进人查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；

② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

注意：

① 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。

【例】单链表中的头结点实际上是一个哨兵

② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。

#include<iostream>
using namespace std;
int main()
{
 int a[]={98,76,109,34,67,190,80,12,14,89,1};
 int k=sizeof(a)/sizeof(a[0]);
 int j;
 for(int i=1;i<k;i++)//循环从第2个元素开始
 {
 if(a[i]<a[i-1])
 {
 int move=a[i];
 for(j=i-1;j>=0 && a[j]>move;j--)//a[j]若小于要挪动的数，则是循环终止的条件
 {
 a[j+1]=a[j];//将a[i]前元素向后挪动一个
 }
 a[j+1]=move;//此处就是a[j+1]=move;
 }
 }
 for(int f=0;f<k;f++)
 {
 cout<<a[f]<<"  ";
 }
 return 0;
}