/*算法思想簡(jiǎn)單描述：
 在要排序的一組數(shù)中，假設(shè)前面(n-1) [n>=2] 個(gè)數(shù)已經(jīng)是排
 好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)
 也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。*/
#include<iostream.h>//直接插入排序
#define MAX 4
void insert_sort(int a[],int n);
int main()
{ 
   int *p, i,n,a[MAX];
   n=MAX;
   p=a;

   cout<<"Input "<<n<<" number for sorting :"<<endl;
   for(i=0;i<MAX;i++)
   {
	 cin>>a[i];
   }
   cout<<endl;
   insert_sort(p,MAX);

   cout<<"After insert_sort:"<<endl;
   for(i=0;i<MAX;i++)
   {
     cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}


void insert_sort(int a[],int n)//直接插入排序
{
   int i,j,t;

   for(i=1;i<n;i++) //要選擇的次數(shù)：1~n-1共n-1次
   { 
      t=a[i];//暫存下標(biāo)為i的數(shù).下標(biāo)從1開始
      for(j=i-1;j>=0&&t<a[j];j--)//注意:j=i-1,j--,這里就是下標(biāo)為i的數(shù),在它前面有序列中找插入位置。
	  {
         a[j+1]=a[j]; //如果滿足條件就往后挪
	  }
      a[j+1]=t; //找到下標(biāo)為i的數(shù)的放置位置
   }
}