基本思想
折半插入排序的基本思想与直接插入排序一样，在插入第个元素已经排好序。区别在于寻找插入位置的方法不同，折半插入排序是采用折半查找法来寻找插入位置的。 折半查找法的基本思路是：用待插元素的值与当前查找序列的中间元素的值进行比较，以当前查找序列的中间元素为分界，确定待插元素是在当前查找序列的左边还是右边，如果是在其左边，则以该左边序列为当前查找序列，，右边也类似。按照上述方法，递归地处理新序列，直到当前查找序列的长度小于1时查找过程结束。
代码(int[] a, int left, int right) {int low, middle, high;int temp;for (int i = left + 1; i <= right; i++) {temp = a[i];low = left;high = i – 1;while (low <= high) {middle = (low + high) / 2;if (a[i] < a[middle])high = middle – 1;elselow = middle + 1;}for (int j = i – 1; j >= low; j–)a[j + 1] = a[j];a[low] = temp;}}性能分析时间复杂度 折半插入排序适合记录数较多的场景，与直接插入排序相比，折半插入排序在寻找插入位置上面所花的时间大大减少，但是折半插入排序在记录移动次数方面和直接插入排序是一样的，所以其时间复杂度为。 其次，折半插入排序的记录比较次数与初始序列无关。因为每趟排序折半寻找插入位置时，折半次数是一定的，折半一次就要比较一次，所以比较次数也是一定的。空间复杂度 同直接插入排序一样，为O。稳定性 折半插入排序是一种稳定的排序算法。
只要看得开放得下，何愁没有快乐的春莺在啼鸣，
