相信大家都了解折半插入排序的定义，即对插入排序算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。本文将从插入排序思想介绍、算法说明、折半插入排序的代码实现这些方面讲解折半插入排序讲解 ，感兴趣的小伙伴就接着看下去吧！
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。
算法说明：
待排序数据： 2 ， 1 ， 6 ， 7 ， 4
取第一个元素作为有序表，剩余的元素作为无序表
其中有序表： 2 ；无序表： 1 ， 6 ， 7 ， 4
第一次比较，从无序表中取出第一个数 1 ，与中间值 2 比较， 1<2 ， 1 插到 2 的前面，得到
有序表： 1 ， 2 ；无序表： 6 ， 7 ， 4
第二次比较，从无序表中取出第一个数 6 ，与中间值 1 比较， 6>1 ，要放在 1 的后面，再与后半区（有序表： 2 ）的中间值 2 比较， 6>2 ， 6 插入到2 的后面，得到
有序表： 1 ， 2 ， 6 ；无序表： 7 ， 4
第三次比较，从无序表中取出第一个数 7 ，与中间值 2 比较， 7>2 ， 7 放在 2 后面，再与后半区（有序表： 6 ）的中间值 6 比较， 7>6 ， 7 放在 6 后面，得到
有序表： 1 ， 2 ， 6 ， 7 ；无序表： 4
第四次比较，从无序表中取出第一个数 4 ，与中间值 2 比较， 4>2 ， 4 放在 2 后面，再与后半区（有序表 :6,7 ）的中间值 6 比较， 4<6 ， 4 放在 6 前面，最终得到：
1 ， 2 ， 4 ， 6 ， 7
折半插入排序的代码实现
1.private void binaryInsertSort(int arr[]){
2.
3. int low = 0;
4. int high = 0;
5. int m = 0;// 中间位置
6. for(int i = 1; i < arr.length; i++){
7. low = 0;
8. high = i-1;
9. while(low <= high){
10. m = (low+high)/2;
11. if(arr[m] > arr[i])
12. high = m - 1;
13. else
14. low = m + 1;
15. }
16. // 统一移动元素，将待排序元素插入到指定位置
17. temp = arr[i];
18. for(int j=i; j > high+1; j--){
19. arr[j] = arr[j-1];
20. }
21. arr[high+1] = temp;
22. }
23. }
总结
折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。
以上就是折半插入排序的干货教程讲解，大家都弄懂了吗？