一个数组有n个元素，假如前面n-1个元素已经排序好了，那么把第n个元素插入到前面n-1个元素，使得数组有序排列，就是插入排序了。

至于n-1个元素如何已经先排序好，那么我们可以假设前面n-2个元素已经排序好，把第n-1个元素插入到前面n-2个元素。

依次类推，直到只剩下一个元素，也就是第一个元素。排序完成。

代码如下：

#include<iostream>
using namespace std;

void Insert_Sort(int *A,int n)
{
	int i,j,a;
	for(i=0;i<n-1;i++)
	{
		j=i+1;
		a=A[j];
	 while(a<A[j-1])
		{
		  A[j]=A[j-1];
		  j--;
		}
	A[j]=a;	
	}
}


void main()
{
	int A[4]={21,2,34,1};
	Insert_Sort(A,4);
	for (int i=0;i<4;i++)
	{
		cout<<A[i]<<endl;
	}
	system("pause");
}

#include<iostream>
using namespace std;

//把n插入前面已经排序好的数组
void Insert(int *a,int n)
{
	int i=n-1;
	int key=a[n];
	while((i>=0)&&key<a[i])
	{
		a[i+1]=a[i];
		i--;
	}
	a[i+1]=key;
	
}


void Insert_Sort(int *A,int n)
{
	if(n>0)
	{
		Insert_Sort(A,n-1); //递归表示前面已经排序好
		Insert(A,n);
	}
	else   //递归的出口是n=0
		return ;
}



void main()
{
	int A[4]={21,2,34,1};
	Insert_Sort(A,3);
	for (int i=0;i<4;i++)
	{
		cout<<A[i]<<endl;
	}
	system("pause");
}

1.最好情况下，原始数据已经排序好，那么时间复杂度为O（N）

2.最坏的情况下，原始数组反向排序，此时为O（n2）

3平均情况下，O（n2）

元素数据在越接近有序的情况下，直接插入的效率越高。

直接插入排序（递归与非递归2种实现方法）