概述
算法介绍与思路推演：
1）假设我们手里的数字是一堆乱序扑克牌，我们想把它整理成从小到大的排序，会怎么办呢，我们会从左往右挨个将牌抽出来插到它合适的位置，这样一轮之后，就变成从小到大的顺序了。
2）程序上怎么实现，从第二位开始，逐个将后一个数和它之前所有的数据进行比较，寻找这个数最合适的插入位置，将其插入空隙，后面的值依次会往后移动一位，循环一遍之后，可实现排序。
二分查找改进版：
如果数组的前面部分已经有序，找到合适的位置这个操作，可以使用二分查找法来找，这样单词查找的效率由O(n)变为O(logn)，其它操作不变
二分查找的逻辑，或者说推算出的特征：
1）四个参数，数组arr，目标值value，起点位置startIndex，终点位置endIndex
2）一开始startIndex和endIndex分别为0和i-1(写排序算法时，尽量设置的值包含边界），因为当前元素就在i的位置，应该在0~i-1个元素之间找。
最终二分查找的返回值应该是0~i之间，因为多了一个当前元素i，所以返回值也是0~i
3）找到一半的位置（startIndex+endIndex）/2，前半部分认为是[0 ~ halfIndex]，后半部分认为是[halfIndex + 1 ~ endIndex]
4）如果value大于等于halfIndex位置的值，则往后找，否则往前找（保证稳定性）
5）直到startIndex == endIndex，这个时候递归应该退出
这个时候判断，如果value仍然大于等于halfIndex的值，那么返回halfIndex + 1
如果vallue小于halfIndex的值，那么value就应该放在halfIndex的位置，返回halfIndex
算法特性：
时间复杂度：
两重循环，所以时间复杂度是O(n^2)
细分一下：(查找 (O(n)或者O(logn)+ 交换目标位置和当前位置元素O(1) + 整体后移(O(n))) * n次，所以是O(n^2)，二分只能一定程度上节约查找的效率，大头其实是交换
所以我们假设只按照交换来计算，最坏的情况是倒序，1+2+3+...+(n-1) = n(n-1) / 2 = O(n^2)
最好的情况顺序，O(n)
稳定性：
代码的实现可以保证稳定性，是稳定的算法
网上有个什么“监视哨”，就是将一个数组自身的元素作为边界，将比较的判断和超出边界合并（一般都是超出边界作为监视哨中的可合并条件），使用一个条件来判断，这样减少一个判断，这个判断在数据量特别大的时候效率提升会很明显。
比如每次从i判断到j>=0，这个j>=0可以和下面的arr[i] >= arr[j]结合起来，也就是把条件放到一个可达到的位置，这样就不用每次判断数组是否越界了。
比如要查找某个元素，直到找到最后一个，我们会判断是否越界，其实可以把这个值放到第0位，如果返回0，认为没找到
这个在插入算法中好像不好用，如果使用二分查找法，这个就没有意义了，并且这玩意要提前复制数组吧。
Java代码实现：
indexSort1为普通的，每次都叫唤，indexSort2为升级后的，捏着当前的值，直到找到合适的位置放下
public static void main(String[] args){
int[] arr = new int[]{10,8,5,1,4,2,3};
System.out.println(Arrays.toString(insertSort1(arr)));
arr = new int[]{10,8,5,1,4,2,3};
System.out.println(Arrays.toString(insertSort2(arr)));
arr = new int[]{10,8,5,1,4,2,3};
System.out.println(Arrays.toString(insertSort3(arr)));
}
/**
* 从第二个数（index=1）开始，逐个向前找到合适的位置放入
* 这个存在的问题是，交换的次数过多，并且可能并不是有效交换
* @param arr
* @return
*/
private static int[] insertSort1(int[] arr){
// 外层循环控制次数
for(int i = 1;i < arr.length;i++){
// 内层循环，找到合适的位置
// 如果不小于最后一个，说明是最大的，直接break
// 如果比前面的小，交换，并继续向前比较，否则逐个向前比较
for(int j = i; j > 0; j--){
if(arr[j] < arr[j - 1]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}else{
// 如果大等于前面一个，直接break
break;
}
}
}
return arr;
}
private static int[] insertSort2(int[] arr){
for(int i = 1;i<arr.length;i++){
// 先捏着最后的位置，找到位置再放下来
int v = arr[i];
int idx = i;
for(int j = i - 1; j >= 0;j--){
// 找到应该插入的位置
if(arr[i] >= arr[j]){
break;
}
// 记录下标
idx = j;
}
// 将到i为止的数据，全部往后移一位
for(int j = i; j > idx; j--){
arr[j] = arr[j - 1];
}
// 将v放下
arr[idx] = v;
}
return arr;
}
/**
* 既然前面有序，可以使用二分查找法，查找到应该放入的位置
* @param arr
* @return
*/
private static int[] insertSort3(int[] arr){
for(int i = 1; i<arr.length ;i++){
int idx = i;
int v = arr[i];
int targetIndex = binarySearch(arr, v, 0, i - 1);
// 如果targetIndex等于i，说明就应该在最后
if(targetIndex == i){
continue;
}
for(int j = i;j > targetIndex;j--){
arr[j] = arr[j - 1];
}
arr[targetIndex] = v;
}
return arr;
}
/**
* 从一般到特殊，推导二分查找的规则
* 1、找到一半的位置，前面为0-halfIndex，后面halfIndex + 1 到 endIndex
* 2、和中间位置比较，如果大于等于，则向后判断，如果小于则向前判断（大于等于，保证稳定性）
* 3、直到startIndex == endIndex，这一步肯定要return，递归结束
* 4、判断如果当前位置大于value，那就是这个位置（有的算法是halfIndex-1)，就不明白了，假设是0的位置，-1不就成负值了，不直观，宏观上讲，找到的位置介于0-i+1之间（i+1是因为一串i的数组现在多了一个元素，当然变成了n+1长度的数组）
* 5、如果是小于等于value，说明推到了最后，返回halfIndex+1
* @param arr
* @param value
* @param startIndex
* @param endIndex
* @return
*/
private static int binarySearch(int[] arr, int value, int startIndex, int endIndex){
int halfIndex= (startIndex + endIndex ) / 2;
// 推到最后一个元素的时候，程序一定要return
if(startIndex == endIndex){
if(arr[halfIndex] <= value){
return halfIndex + 1;
}else{
return halfIndex;
}
}
if(value >= arr[halfIndex]){
return binarySearch(arr, value, halfIndex + 1, endIndex);
}else{
return binarySearch(arr, value, 0, halfIndex);
}
}
最后
以上就是精明电源为你收集整理的插入排序--简单插入排序+二分插入排序算法介绍与思路推演：算法特性：Java代码实现：的全部内容，希望文章能够帮你解决插入排序--简单插入排序+二分插入排序算法介绍与思路推演：算法特性：Java代码实现：所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复