带哨兵的直接插入排序法
排序原理:其实也属于插入法类型,分已排序和未排序部分,只不过初次把
第二个元素当作已排好序部分.牺牲数组的第一个元素作为监视
哨兵,作用类似于直接插入法排序中的temp,用哨兵的作用是可
以避免检查时可能出现数组越界的情况,比如数组下表可能出现
小于0的数值(如-1).
-------------------------------------------------------------------------------------------*/
#include<stdio.h>
void With_Sentry_Sort(int ar[],int len);
int main(void)
{
int i,n;
puts("Input the number of elements to the array:");
scanf("%d",&n);
int ar[n];
puts("Input n numbers:");
for(i=0;i<n;i++) //读取数组元素
scanf("%d",&ar[i]);
With_Sentry_Sort(ar,n);
printf("ar[%d] = ",n);
for(i=0;i<n;i++) //逐个打印数组元素
printf("%d ",ar[i]);
putchar('\n');
return 0;
}
void With_Sentry_Sort(int ar[],int len)//带哨兵排序
{
int i,j,temp;
for(i=2;i<len;i++)
{
ar[0]=ar[i]; //数组的第一个元素用来做监视哨兵
for(j=i-1;ar[j]>ar[0];j--) //插入排序法,当j减小到0时便会跳出循环,不会出现j<0的情况
{
ar[j+1]=ar[j];
ar[j]=ar[0];
}
}
}