【游戏算法】编码实现直接插入排序

参考答案：

直接插入排序编程实现如下：

#include<iostream.h> 
void main( void ) 
{ 
 	int ARRAY[10] = { 0, 6, 3, 2, 7, 5, 4, 9, 1, 8 }; 
 	int i,j; 
 	for(  i = 0; i < 10; i++) 
 	{ 
 	 	cout<<ARRAY[i]<<" "; 
 	} 
 	cout<<endl; 
	
	//将 ARRAY[2],…,ARRAY[n]依次按序插入 
 	for( i = 2; i <= 10; i++ ) 	
 	{  	 
		//如果 ARRAY[i]大于一切有序的数值
		//ARRAY[i]将保持原位不动 
 	 	if(ARRAY[i] < ARRAY[i-1]) 	
 	 	{ 
			//将 ARRAY[0]看做是哨兵,是 ARRAY[i]的副本    
			j = i - 1; 
			ARRAY[0] = ARRAY[i];  
 	 	 	do
			{  	 	 	 	 	
				//从右向左在有序区 ARRAY[1．．i-1]中  
				//查找 ARRAY[i]的插入位置 
				ARRAY[j+1] = ARRAY[j];  //将数值大于 ARRAY[i]记录后移    
				j-- ; 
 	 	 	}while( ARRAY[0] < ARRAY[j] );  
			
			//ARRAY[i]插入到正确的位置上 
 	 	 	ARRAY[j+1]=ARRAY[0];  	
 	 	} 
 	} 
 	for(  i = 0; i < 10; i++) 
 	{ 
 	 	cout<<ARRAY[i]<<" "; 
 	} 
 	cout<<endl; 
}

注意：所有为简化边界条件而引入的附加结点（元素）均可称为哨兵。引入哨兵后使得查找循环条件的时间大约减少了一半，对于记录数较大的文件节约的时间就相当可观。类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技。