这篇文章将为大家详细讲解有关java实现插入排序后如何进一步优化，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
站在用户的角度思考问题，与客户深入沟通，找到荔波网站设计与荔波网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都网站制作、做网站、外贸营销网站建设、企业官网、英文网站、手机端网站、网站推广、空间域名、雅安服务器托管、企业邮箱。业务覆盖荔波地区。
最朴素的版本：从数组的第二个元素进行操作，一旦发现其前面的元素比他大，就交换。
static int[] insertSort(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int cur = begin;
while (cur > 0 && array[cur] < array[cur-1]){
int tmp = array[cur];
array[cur] = array[cur-1];
array[cur-1] = tmp;
cur--;
}
}
return array;
}第一步优化：从数组的第二个元素进行操作，如果发现其前面的元素比他大，就将其前面的元素往后挪，直到cur指向的元素大于或者等于他前一个元素，此时cur指向的位置就是待插入元素应该插入的位置。
static int[] insertSort2(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int cur = begin;
int tmp = array[cur];
while (cur > 0 && array[cur] < array[cur-1]){
array[cur] = array[cur-1];
cur--;
}
array[cur] = tmp;
}
return array;
}第二步优化
第三种算法和第二种其实本质上是一样的，都是找待插入位置，挪动元素，只不过第三种算法通过二分查找减少了比较次数，即cmp函数的调用，还减少了swap函数的调用。更快的找到了当前元素应该插入的位置，然后再进行挪动，提高了效率。
static int[] insertSort3(int[] array){
int len = array.length;
for (int begin = 1; begin < len; begin++){
int v = array[begin];
int insertIndex = search(array,begin);
// 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位
for (int i = begin; i > insertIndex; i--){
array[i] = array[i-1];
}
array[insertIndex] = v;
}
return array;
}
static int search(int[] array, int index){
int begin = 0;
int end = index;
while(begin < end){
int mid = (begin+end) >> 1;
if (array[index] < array[mid]){
end = mid;
}else{
begin = mid+1;
}
}
return begin;
}需要注意的是：使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是O(n^2)
将其中的挪动操作分离出来的效果：
