直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
public static void insertionSort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int j = i;
while (j > 0 && arr[j] < arr[j - 1])
{
swap(arr,j,j-1);
j--;
}
}
}
或
void InsertSort(int arr[],int n)
{
for (int i =1;i <= n;++i)
{
for(int j = i;j > 0;--j)
{
if(arr[j] < arr[j -1])
{
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
原理都是一样的，第一个for循环对从第二个开始的所有的数字遍历，嵌套的for循环是每次遍历数字时都取无序区的一个元素与有序区的元素比较，如果比有序区的要小则交换，直到合适的位置。
如果使用vector的话会方便一点，因为vector可以使用size()直接获得容器内的元素个数
void InsertSort2(vector<int> &num)
{
for(int i = 1;i < num.size();++i)
{
for(int j = i;j > 0;--j)
{
if(num[j] < num[j - 1])
{
int temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
}
}
}
}
插入排序的时间复杂度最好的情况是已经是正序的序列，只需比较(n-1)次，时间复杂度为O(n)，最坏的情况是倒序的序列，要比较n(n-1)/2次，时间复杂度为O(n^2 ) ，平均的话要比较时间复杂度为O(n^2 )
插入排序是一种稳定的排序方法，排序元素比较少的时候很好，大量元素便会效率低下
