直接插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)
稳定性
直接插入排序是稳定的，不会改变相同元素的相对顺序。
算法优化：
二分查找插入排序的原理：是直接插入排序的一个变种，在有序区中查找新元素插入位置时，为了减少元素比较次数提高效率，采用二分查找算法进行插入位置的确定。
/**
* 二分查找插入排序
* @param sortList
*/
public static void insertSort3(Integer[] sortList) {
int len = sortList.length;
for (int i = 1; i < len; i++) {
if (sortList[i] < sortList[i - 1]) {
//二分查找在有序区寻找插入的位置
int index = binarySearchIndex(sortList, i-1, sortList[i]);
if (i != index)
{
int temp = sortList[i];
// 后移元素，腾出arr[index]位置
for (int j = i - 1; j >= index; j--)
sortList[j + 1] = sortList[j];
// 将 arr[i] 放到正确位置上
sortList[index] = temp;
}
}
}
}
/**
* 二分查找要插入的位置得index
* @param sortList
* @param maxIndex
* @param data
* @return
*/
private static int binarySearchIndex(Integer[] sortList, int maxIndex, int data)
{
int iBegin = 0;
int iEnd = maxIndex;
int middle = -1;
while (iBegin <= iEnd)
{
middle = (iBegin + iEnd) / 2;
if (sortList[middle] > data)
{
iEnd = middle - 1;
}
else
{
iBegin = middle + 1;// 如果是相同元素，也是插入在后面的位置
}
}
return iBegin;
}
算法复杂度
1、时间复杂度：O(n^2)
二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数），即O(log2n)。所以，二分查找排序比较次数为：x=log2n。
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：
1)最好情况：查找的位置是有序区的最后一位后面一位，则无须进行后移赋值操作，其比较次数为：log2n ，即O(log2n)。
2)最坏情况：查找的位置是有序区的第一个位置，则需要的比较次数为：log2n，需要的赋值操作次数为n(n-1)/2加上 (n-1) 次，即O(n^2)。
3)渐进时间复杂度（平均时间复杂度）：O(n^2)。
2、空间复杂度：O(1)
二分查找插入排序是在原输入数组上进行后移赋值操作的（称“就地排序”），所需开辟的辅助空间跟输入数组规模无关，所以空间复杂度为：O(1)。
稳定性
二分查找排序是稳定的，不会改变相同元素的相对顺序。
相关附件直接插入排序下载：
------------------------------------------分割线------------------------------------------