在线客服
扫描二维码
下载博学谷APP扫描二维码
关注博学谷微信公众号
相信大家都了解折半插入排序的定义,即对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。本文将从插入排序思想介绍、算法说明、折半插入排序的代码实现这些方面讲解折半插入排序讲解 ,感兴趣的小伙伴就接着看下去吧!
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置。
算法说明:
待排序数据: 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基础 ArrayList,Vector, LinkedList 的存储性能和特性是什么?
这样的题比较考水平,两个方面的水平:一是要真正明白这些内容,二是要有较强的总结和表述 能力。如果你明白,但表述不清楚,在别人那里则等同于不明白。
10001
2019-06-03 11:18:58
SpringMVC面试题集锦
Spring MVC是spring框架的一个模块,是基于MVC的轻量级Web框架。Spring是目前Web开发中的一个很重要的部分。尤其在企业招聘相关开发者的时候,有大量的笔试和面试题目都与springMVC有关,下面是小编为大家整理的关于springMVC的一些面试题!
6086
2019-11-19 18:29:43
Java基础语法之if语句学习笔记
众所周知,流程控制语句可以分为三类,分别是顺序结构、分支结构和循环结构,而分支结构又可以分为if语句和switch语句。顺序结构可以说是程序中最简单最基本的流程控制,这里就不展开详细讲解了。本文重点要讲解分析的是分支结构的if语句,内容包括了if语句的格式、执行流程和具体示例。想要学习Java基础语法的小伙伴,可以看看下面整理的if语句的笔记,希望对大家入门Java能够有所帮助。
6678
2019-12-06 12:40:32
这样的Java自学姿势 学废最快
学习Java人数最多。原因是?自然是Java长久占据界编程语言排行榜中榜首,且众多互联网一线大厂如阿里、京东、美团、滴滴等都在使用Java架构。世间的一切,终究逃不过一个“钱”字。
3957
2021-03-05 11:27:54
狂野架构师课程厉害吗?能学到哪些技能?
目前职场中有很多Java程序员遇到职业瓶颈,⼀直在中⼩公司,写着重复的业务代码,未参与过⼤型互联⽹项⽬,技术成⻓缓慢,发展遇到瓶颈。如⼯作2-5年的⼯程师不能满⾜企业实际要求,技术不够深⼊实际业务经验⽋缺。
5061
2022-09-29 16:51:24