基本思路：有序部分（刚开始有序部分的长度为0）的下一个数b如果小于有序部分的最后一个数a，则交换这两个数，b前进一位。交换后，若此时b仍小于b前面的数，则交换这两个数，b又前进一位。一直到b大于b前面的数或b到达位置0，则停止交换，这个过程相当于把数b插入到有序部分中。有序部分的长度加一。继续循环直到有序部分的长度等于数组的长度，此时数组有序。
图示：
代码：
public static void insertSort(int []arr)
{
if(arr==null||arr.length<2)//传入空指针或数组长度小于2直接返回。
return ;
for(int i=1;i0&&arr[i]
时间复杂度：for循环中有while循环，通过while循环不断把有序部分的后一个数插入有序部分中，O(n^2)
空间复杂度：只用了有限几个变量，O(1)
