算法的基本过程：
1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 …….快速的确定出第 i 个元素要插在什么地方；
3）确定位置之后，将整个序列后移，并将元素插入到相应位置。
时间复杂度O(n^2)
附加空间O(1)
本来我觉得折半插入排序是特别简单点的，但是发现自己写起代码来特别费劲，然后就去翻书看博客，发现大家对折半插入的讲解都没有特别的透彻，在此写一篇博客来记录下折半插入排序的详细过程。我们先来看看各位前辈大牛的代码吧！针对重点关键代码我来为大家做详细的解释。
1 2 3 | public static void halfInsertSort(int[] arr ) { int size = arr.length; int low, high, mid; for(int i=2;i<size;i++){ low = 1; high = i-1; arr[0] = arr[i];//哨兵复制 while(low<=high){ mid = (low+high)/2; if(arr[0]>arr[mid]){ low = mid+1; } else { high = mid – 1; } } for(int j = i;j>high+1;j–){ arr[j] = arr[j-1]; } arr[high+1] = arr[0]; } } |
1、为什么要从2开始算起，不应该是1吗？
其实你会看到有的人写这个算法的时候是从1开始，但有更多的代码写的是从2开始，目的是第0个元素腾出来作为哨兵（该哨兵不在已排序队列内），第一个元素只有一个元素不用排，所以从第二个元素开始。
2、为什么要放一个哨兵
有的代码不放哨兵，不放哨兵就需要判断high下表是否出界，而放了哨兵就完全不用担心出界的问题，这样能提高代码的性能。举个不放哨兵的例子：已排好序的13 16，现在要插入9，按照上面的算法，low指向第0个元素13，high指向第一个元素16，mid指向0号元素，判断发现9比13小，所以high=mid-1=-1。越界了！！！但是如果放了哨兵呢？low =1;high =2,mid =1岁,high=mid-1=0，没有越界，此时low>high，跳出循环。
明白了放哨兵的作用了吧！
3、为什么j的范围是从i到high
首先看看我们的while语句，条件是low<=high，也就是说只有high<low的时候才会停止while循环，而high<low是因为目标值小于arr[mid]导致的。再来分析下，什么情况下high就小于low了呢？肯定是mid值和low相等了，也就是说：目标值应该插在low的前面，也就是目前high值的后面。可能大家有di点晕了。跳出循环的最后一幕：
跳出后，high就变成了mid-1了。因此应该把目标元素插在mid指向的位子，也就是跳出while循环后的high+1的地方。所以high+1（包括high+1）的后面的数组整体应该向后移一位。因此第high+1个元素再等于目标元素。
还有些问题：
1、一般来说输入的数组都会是一个乱序的数组，不会是故意将第0号元素空出来，所以这个代码从某种意义上说还不算完美。
所以，我写的完整代码如下：
|
1
|
public class HalfInserSort {
for(int i=2;i<size;i++){ |
这里可能有点费解，
//把tempArr加入：
与前面的向后移动一个位子是一个意思，找到插入的位子，将这个位子之前的所有元素向前移动，将目标元素插入到这个位子上。
L[0]L[1,..,target,…n-1] 左移之后：
如果有什么写的不对的，还请指正
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/10719.html
