插入排序算法
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
折半插入排序
将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。在处理A[i]时，A[0]……A[i-1]已经按关键码值排好序。所谓折半比较，就是在插入A[i]时，取A[i-1/2]的关键码值与A[i]的关键码值进行比较，如果A[i]的关键码值小于A[i-1/2]的关键码值，则说明A[i]只能插入A[0]到A[i-1/2]之间，故可以在A[0]到A[i-1/2-1]之间继续使用折半比较；否则只能插入A[i-1/2]到A[i-1]之间，故可以在A[i-1/2+1]到A[i-1]之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在A[k]和A[r]之间采用折半，其中间结点为A[k+r/2]，经过一次比较即可排除一半纪录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是文件纪录必须按顺序存储。
算法复杂度：O（n2）
算法思想：
- 计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
- 在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方；
- 确定位置之后，将整个序列后移，并将元素插入到相应位置。
/**
* 二分插入排序
* 2017年8月23日 下午9:20:29
*
*/
public class BinaryInsertSort> {
/**
* 二分插入排序算法
* @param array
*/
public void binaryInsertSort(T[] array) {
// 循环数组
for (int i = 0; i < array.length; i++) {
// 将当前元素进行保存
T temp = array[i];
// 初始化左下标
int left = 0;
// 初始化右下标为当前元素的上一个元素的下标
int right = i - 1;
// 初始化中间下标
int middle = 0;
// 当左下标小于等于右下标时循环
// 大于时表示已经找到
while (left <= right) {
// 中下标为左右下标区间的中间位置下标
middle = (left + right) / 2;
// 如果i位置元素小于中间下标元素
if (temp.compareTo(array[middle]) == -1) {
// 将右下标设置为中间下标的上一个元素下标
right = middle - 1;
// 如果i位置元素大于中间下标元素
} else {
// 将左下标设置为中间下标的下一个元素下标
left = middle + 1;
}
}
// 从当前元素位置到要插入的位置，循环将元素向后挪动一个位置
for (int j = i; j > left; j--) {
// 向后挪动一个位置
array[j] = array[j - 1];
}
// 如果要插入的位置不为当前位置
// 如果相等，则为该位置未动
if (left != i) {
// 元素插入
array[left] = temp;
}
}
}
public static void main(String[] args) {
Integer[] array = { -1, 45, -78, 54, 7, 5, 3, 4, 5, 454, 87, 1, 854, 87,
-15 };
BinaryInsertSort sort = new BinaryInsertSort();
sort.binaryInsertSort(array);
for (Integer integer : array) {
System.out.println(integer);
}
}
}
