学步园

/*--------------------------------------------------------------------------------------------
                      带哨兵的直接插入排序法
排序原理:其实也属于插入法类型,分已排序和未排序部分,只不过初次把
                 第二个元素当作已排好序部分.牺牲数组的第一个元素作为监视
                 哨兵,作用类似于直接插入法排序中的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];
		}
	}
}