数组排序(2) 直接插入排序

---

算法思想：直接将待插入的元素插入到有序数组中

1. 通常我们都以首元素为第一个有序数组，将第二个元素插入到这个有序数组中。
2. 以数组前两个元素构成第二个有序数组，将第三个元素插入到这个有序数组中。
3. 以数组前三个元素构成第三个有序数组，将第四个元素插入到这个有序数组中。
4. 一直到以数组前（n-1）个元素构成第（n-1）个有序数组，将最后一个元素插入到这个有序数组中。

代码实现：

void insran(int arr[], int len){
	if(!arr || k<=0)
		return ;
	for(int i=1; i<len; i++)
		if(arr[i]<arr[i-1]){
			int k=i;
			for(int j=k-1; j>=0; j--,k--)
				if(arr[k]<arr[j]){
					arr[k]+=arr[j];
					arr[j]=arr[k]-arr[j];
					arr[k]-=arr[j];
				}
		}
}

时间复杂度：

外层for循环执行次数为（n-1）次，最坏的情况：内层for循环执行次数为1次到（n-1）次。循环执行总次数为,时间复杂度为O(n^2)。