思路：
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 插入排序方法分直接插入排序和折半插入排序两种。
直接插入排序
直接插入排序
代码：
public class Insertion_sort {
public static void main(String[] args) {
int[] sortArray = new int[10000];
for(int i = 0; i < 10000; i++){
sortArray[i] = (int) (Math.random()*1000);
}
insertionSort(sortArray);
print(sortArray);
}
private static void insertionSort(int[] array){
for(int i = 1; i < array.length; i++){
for(int j = i; j > 0 && array[j] < array[j - 1];j--){
swap(array, j, j -1);
}
}
}
private static void swap(int[] array, int i, int j) {
array[i] = array[i]^array[j];
array[j] = array[j]^array[i];
array[i] = array[i]^array[j];
}
private static void print(int[] sortArray) {
for(int i = 0; i < sortArray.length; i++){
System.out.print(i == sortArray.length - 1 ? sortArray[i] : (sortArray[i]+" , "));
}
}
}
折半插入排序
如果在最复杂的情况下，所要排序的整个数列是逆序的，当第 i-1 趟需要将 第 i 个元素插入前面的 0~ i -1 个元素的序列当中的时候，它总是会从第 i -1 个元素开始，逐个比较每个元素的大小，直到找到相应的位置。 直接插入算法中丝毫没有考虑当要插入第 i 个元素时前面的 0~~ i -1 序列是有序的这个特点。折半插入排序算法就充分的利用了这一点。
算法的基本过程：
1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半； 2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方； 3）确定位置之后，将整个序列后移，并将元素插入到相应位置。
代码：
private static void binaryInsertSort(int[] sortArray){
//保存中间插入的值
int insertNote = 0;
for(int i = 1; i < sortArray.length; i++){
int low = 0;
int high = i - 1;
insertNote = sortArray[i];
//不断折半
while(low <= high){
//中间位置
int mid = (low + high) / 2;
if(sortArray[i] < sortArray[mid]){
//在小于中间值那部分查找
high = mid - 1;
}
else{
//在大于中间值那部分查找
low = mid + 1;
}
}
//使插入点之后的数组往后推移一位（包括插入点）
for(int j = i; j > low; j--){
sortArray[j] = sortArray[j - 1];
}
//插入到指定的位置
sortArray[low] = insertNote;
}
}
算法分析：
1）时间复杂度： 折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。
2）空间复杂度： 折半插入排序和插入排序一样只需要一个多余的缓存数据单元来放第 i 个元素，所以空间复杂度是O（1），因为排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，所以它是一个稳定排序。
