原创 折半插入排序讲解 干货教程

发布时间:2019-07-30 11:10:06 浏览 5058 来源:博学谷资讯 作者:照照

    相信大家都了解折半插入排序的定义,即对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。本文将从插入排序思想介绍、算法说明、折半插入排序的代码实现这些方面讲解折半插入排序讲解 ,感兴趣的小伙伴就接着看下去吧!

     

    折半插入排序讲解

     

    插入排序思想介绍

     

    折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置。

     

    算法说明:

     

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

     

    总结

     

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

     

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

    申请免费试学名额    

在职想转行提升,担心学不会?根据个人情况规划学习路线,闯关式自适应学习模式保证学习效果
讲师一对一辅导,在线答疑解惑,指导就业!

上一篇: 组合模式深度解析 下一篇: Java程序员培训完好就业吗?

相关推荐 更多

热门文章

  • 清华应届生要求月薪3万+期权,被HR狂喷
  • 大学生就业调研报告,超六成大学生认为自己十年后是这个薪资
  • 整洁代码有多重要,看了这个你就懂了
  • C++的校招的面试题,看看你能答对几个?
  • TIOBE 9月编程语言排名!它终于出圈了
  • 9月份的数据库排名来啦!速来围观
  • 值得收藏的程序开发的利器,你都有吗?
  • 程序员薪资又创新高?!这次竟然有462万元
  • 如何成为人类高质量成员?喵!
  • 双码农家庭20年就能实现财务自由?这是真的么?
  • 查看更多

扫描二维码,了解更多信息

博学谷二维码