【图灵干货】折半插入排序讲解

　　我们相信大家已经熟悉了折半插入排序的定义，也就是对插入排序算法的一种改进，所谓排序算法，就是不停地将元素按顺序插入先前排列的顺序。这篇文章将从介绍插入排序的思想，算法说明，折半插入排序代码实现以上方面讲解折半插入排序讲解，感兴趣的小伙伴就继续看下去!

　　插入分类介绍思想。

　　折叠半插入排序与直接插入排序算法的原理相同。不过，当将数据插入到已排序的数据时，使用来对半查询进行二分查找。首先将已排序序列的中间元素与要插入的数据相比较，如果中间元素的值比要大，那么这个待插入的数据属于数组的前一半，否则它就属于后半部分。连续模拟，不断缩小距离，确定想要插入的位置。

算法说明：

　　待排序数据： 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. }

　　总结

　　折半插入排序相对稳定，相对于直接插入排序，减少了比较次数;但是相对直接插入排序，移动次数不变。

　　以上就是折半插入排序的干货教程讲解，大家都弄懂了吗?